{x}
blog image

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 104
  • 0 <= value <= 105
  • At most 2 * 105 calls will be made to get and put.

146. LRU Cache

Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Solutions

Solution 1: Hash Table + Doubly Linked List

This solution uses a hash table and a doubly linked list to achieve O(1) time complexity for both get and put operations.

  • Hash Table: Stores the key-node mappings for fast key lookups (O(1) on average). The key is the integer key, and the value is a pointer/reference to the corresponding node in the doubly linked list.
  • Doubly Linked List: Maintains the order of usage. The most recently used item is at the head, and the least recently used is at the tail. Using a doubly linked list allows for efficient insertion and deletion at both ends (O(1)).

Operations:

  • get(key):

    1. Check if the key exists in the hash table. If not, return -1.
    2. If the key exists, get the corresponding node from the hash table.
    3. Move the node to the head of the doubly linked list (making it the most recently used).
    4. Return the node's value.

  • put(key, value):

    1. Check if the key exists in the hash table.
      • If it exists, update the node's value and move the node to the head.
      • If it doesn't exist:
        1. Create a new node with the key-value pair.
        2. Add the new node to the head of the doubly linked list.
        3. Add the key-node mapping to the hash table.
        4. If the cache size exceeds the capacity, remove the least recently used node (tail) from the list and hash table.

Time Complexity: O(1) for both get and put on average. Hash table lookups and doubly linked list operations are O(1) on average.

Space Complexity: O(capacity) to store the cache entries.

Python3

class Node:
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
 
class LRUCache:
 
    def __init__(self, capacity: int):
        self.size = 0
        self.capacity = capacity
        self.cache = {}  # Hash table
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.remove_node(node)
        self.add_to_head(node)
        return node.val
 
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            self.remove_node(node)
            node.val = value
            self.add_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                node = self.tail.prev
                self.cache.pop(node.key)
                self.remove_node(node)
                self.size -= 1
 
    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next = node
        node.next.prev = node

Java

class Node {
    int key, val;
    Node prev, next;
 
    Node() {}
 
    Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
 
class LRUCache {
    private int size;
    private int capacity;
    private Node head = new Node();
    private Node tail = new Node();
    private Map<Integer, Node> cache = new HashMap<>();
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
 
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        removeNode(node);
        addToHead(node);
        return node.val;
    }
 
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            removeNode(node);
            node.val = value;
            addToHead(node);
        } else {
            Node node = new Node(key, value);
            cache.put(key, node);
            addToHead(node);
            if (++size > capacity) {
                node = tail.prev;
                cache.remove(node.key);
                removeNode(node);
                size--;
            }
        }
    }
 
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

C++

class LRUCache {
private:
    struct Node {
        int key, val;
        Node* prev;
        Node* next;
        Node(int key, int val) : key(key), val(val), prev(nullptr), next(nullptr) {}
    };
 
    int size;
    int capacity;
    Node* head;
    Node* tail;
    unordered_map<int, Node*> cache;
 
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
 
    void addToHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
 
public:
    LRUCache(int capacity) : size(0), capacity(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
 
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        Node* node = cache[key];
        removeNode(node);
        addToHead(node);
        return node->val;
    }
 
    void put(int key, int value) {
        if (cache.count(key)) {
            Node* node = cache[key];
            removeNode(node);
            node->val = value;
            addToHead(node);
        } else {
            Node* node = new Node(key, value);
            cache[key] = node;
            addToHead(node);
            if (++size > capacity) {
                Node* nodeToRemove = tail->prev;
                cache.erase(nodeToRemove->key);
                removeNode(nodeToRemove);
                size--;
            }
        }
    }
};

Go

type Node struct {
	key, val int
	prev, next *Node
}
 
type LRUCache struct {
	size, capacity int
	head, tail *Node
	cache map[int]*Node
}
 
func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head
	return LRUCache{
		capacity: capacity,
		head: head,
		tail: tail,
		cache: make(map[int]*Node),
	}
}
 
func (this *LRUCache) Get(key int) int {
	if node, ok := this.cache[key]; ok {
		this.removeNode(node)
		this.addToHead(node)
		return node.val
	}
	return -1
}
 
func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.cache[key]; ok {
		this.removeNode(node)
		node.val = value
		this.addToHead(node)
	} else {
		node := &Node{key: key, val: value}
		this.cache[key] = node
		this.addToHead(node)
		if this.size++; this.size > this.capacity {
			node = this.tail.prev
			delete(this.cache, node.key)
			this.removeNode(node)
			this.size--
		}
	}
}
 
func (this *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}
 
func (this *LRUCache) addToHead(node *Node) {
	node.next = this.head.next
	node.prev = this.head
	this.head.next = node
	node.next.prev = node
}

TypeScript

class Node {
    key: number;
    val: number;
    prev: Node | null;
    next: Node | null;
 
    constructor(key: number, val: number) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}
 
class LRUCache {
    size: number;
    capacity: number;
    head: Node;
    tail: Node;
    cache: Map<number, Node>;
 
    constructor(capacity: number) {
        this.size = 0;
        this.capacity = capacity;
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.cache = new Map();
    }
 
    get(key: number): number {
        if (!this.cache.has(key)) {
            return -1;
        }
        const node = this.cache.get(key)!;
        this.removeNode(node);
        this.addToHead(node);
        return node.val;
    }
 
    put(key: number, value: number): void {
        if (this.cache.has(key)) {
            const node = this.cache.get(key)!;
            this.removeNode(node);
            node.val = value;
            this.addToHead(node);
        } else {
            const node = new Node(key, value);
            this.cache.set(key, node);
            this.addToHead(node);
            if (++this.size > this.capacity) {
                const last = this.tail.prev!;
                this.cache.delete(last.key);
                this.removeNode(last);
                this.size--;
            }
        }
    }
 
    removeNode(node: Node): void {
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }
 
    addToHead(node: Node): void {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next!.prev = node;
        this.head.next = node;
    }
}

Rust

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;
 
struct Node {
    key: i32,
    val: i32,
    prev: Option<Rc<RefCell<Node>>>,
    next: Option<Rc<RefCell<Node>>>,
}
 
impl Node {
    fn new(key: i32, val: i32) -> Self {
        Self { key, val, prev: None, next: None }
    }
}
 
struct LRUCache {
    capacity: i32,
    map: HashMap<i32, Rc<RefCell<Node>>>,
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}
 
 
impl LRUCache {
    fn new(capacity: i32) -> Self {
        Self { capacity, map: HashMap::new(), head: None, tail: None }
    }
 
    fn get(&mut self, key: i32) -> i32 {
        if let Some(node) = self.map.get(&key) {
            let node = Rc::clone(node);
            self.remove(&node);
            self.add_to_head(&node);
            node.borrow().val
        } else {
            -1
        }
    }
 
    fn put(&mut self, key: i32, value: i32) {
        if let Some(node) = self.map.get(&key) {
            let node = Rc::clone(node);
            node.borrow_mut().val = value;
            self.remove(&node);
            self.add_to_head(&node);
        } else {
            let node = Rc::new(RefCell::new(Node::new(key, value)));
            self.map.insert(key, Rc::clone(&node));
            self.add_to_head(&node);
            if self.map.len() as i32 > self.capacity {
                let last = self.remove_last();
                self.map.remove(&last.borrow().key);
            }
        }
    }
 
    fn add_to_head(&mut self, node: &Rc<RefCell<Node>>) {
        let mut new_head = Rc::clone(node);
        new_head.borrow_mut().next = self.head.clone();
        if let Some(head) = self.head.clone() {
            head.borrow_mut().prev = Some(Rc::clone(&new_head));
        }
        self.head = Some(new_head);
        if self.tail.is_none() {
            self.tail = self.head.clone();
        }
    }
 
    fn remove(&mut self, node: &Rc<RefCell<Node>>) {
        if let Some(prev) = &node.borrow().prev {
            prev.borrow_mut().next = node.borrow().next.clone();
        } else {
            self.head = node.borrow().next.clone();
        }
        if let Some(next) = &node.borrow().next {
            next.borrow_mut().prev = node.borrow().prev.clone();
        } else {
            self.tail = node.borrow().prev.clone();
        }
    }
 
 
    fn remove_last(&mut self) -> Rc<RefCell<Node>> {
        let last = self.tail.clone().unwrap();
        self.remove(&last);
        last
    }
}

JavaScript

class Node {
    key;
    val;
    prev;
    next;
    constructor(key, val) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}
 
class LRUCache {
    size;
    capacity;
    head;
    tail;
    cache;
    constructor(capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.cache = new Map();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    get(key) {
        if (!this.cache.has(key)) return -1;
        const node = this.cache.get(key);
        this.remove(node);
        this.add(node);
        return node.val;
    }
    put(key, value) {
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            node.val = value;
            this.remove(node);
            this.add(node);
        } else {
            const node = new Node(key, value);
            this.cache.set(key, node);
            this.add(node);
            if (this.size === this.capacity) {
                this.remove(this.tail.prev);
                this.size--;
            }
            this.size++;
        }
    }
    remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    add(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }
}

C#

public class LRUCache {
    private int capacity;
    private Dictionary<int, Node> cache = new Dictionary<int, Node>();
    private Node head = new Node(0, 0);
    private Node tail = new Node(0, 0);
    private int count = 0;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
 
    public int Get(int key) {
        if (!cache.ContainsKey(key)) return -1;
        var node = cache[key];
        remove(node);
        add(node);
        return node.val;
    }
 
    public void Put(int key, int value) {
        if (cache.ContainsKey(key)) {
            var node = cache[key];
            node.val = value;
            remove(node);
            add(node);
        }
        else {
            var node = new Node(key, value);
            cache.Add(key, node);
            add(node);
            if (count == capacity) {
                remove(tail.prev);
                count--;
            }
            count++;
        }
    }
 
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        cache.Remove(node.key);
    }
 
    private void add(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
        cache.Add(node.key, node);
    }
 
    private class Node {
        public int key;
        public int val;
        public Node prev;
        public Node next;
 
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}