LRU Cache
Medium Top 250
Problem 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 sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Examples
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]
Constraints
1 <= capacity <= 30000 <= key <= 10⁴0 <= value <= 10⁵- At most
2 * 10⁵calls will be made togetandput.
Hash Map and Doubly Linked List
To achieve O(1) time complexity for both get and put operations:
- We use a Hash Map to lookup nodes by their key in O(1) time.
- We use a Doubly Linked List to maintain the order of elements based on recency.
- The head of the list points to the most recently used (MRU) node.
- The tail of the list points to the least recently used (LRU) node.
When a key is accessed (via
getorput), we lookup its node in the hash map, disconnect it from its current position in the list, and move it to the head of the list. When inserting a new key that exceeds capacity, we evict the node at the tail of the list, remove its entry from the hash map, and insert the new node at the head.
Solution 1: Hash Map with Doubly Linked List
Pair a hash map with a doubly linked list to support O(1) cache lookups and updates.
import java.util.HashMap;
class LRUCache {
private static class Node {
int key, val;
Node prev, next;
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private final int capacity;
private final HashMap<Integer, Node> map;
private final Node head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.head = new Node(0, 0); // dummy head
this.tail = new Node(0, 0); // dummy tail
head.next = tail;
tail.prev = head;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void insertAtHead(Node node) {
node.next = head.next;
node.next.prev = node;
head.next = node;
node.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
remove(node);
insertAtHead(node); // mark as most recently used
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
remove(node);
insertAtHead(node);
} else {
if (map.size() == capacity) {
Node lru = tail.prev; // evict least recently used node
remove(lru);
map.remove(lru.key);
}
Node newNode = new Node(key, value);
insertAtHead(newNode);
map.put(key, newNode);
}
}
}class Node:
def __init__(self, key: int, val: int):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.map = {}
self.head = Node(0, 0) # dummy head
self.tail = Node(0, 0) # dummy tail
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: Node):
node.prev.next = node.next
node.next.prev = node.prev
def _insert_at_head(self, node: Node):
node.next = self.head.next
node.next.prev = node
self.head.next = node
node.prev = self.head
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._insert_at_head(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.map:
node = self.map[key]
node.val = value
self._remove(node)
self._insert_at_head(node)
else:
if len(self.map) == self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]
new_node = Node(key, value)
self._insert_at_head(new_node)
self.map[key] = new_node#include <unordered_map>
class LRUCache {
private:
struct Node {
int key, val;
Node* prev;
Node* next;
Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};
int capacity;
std::unordered_map<int, Node*> map;
Node* head;
Node* tail;
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insertAtHead(Node* node) {
node->next = head->next;
node->next->prev = node;
head->next = node;
node->prev = head;
}
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (map.find(key) == map.end()) return -1;
Node* node = map[key];
remove(node);
insertAtHead(node);
return node->val;
}
void put(int key, int value) {
if (map.find(key) != map.end()) {
Node* node = map[key];
node->val = value;
remove(node);
insertAtHead(node);
} else {
if (map.size() == capacity) {
Node* lru = tail->prev;
remove(lru);
map.erase(lru->key);
delete lru;
}
Node* newNode = new Node(key, value);
insertAtHead(newNode);
map[key] = newNode;
}
}
};Complexity Analysis
- Time Complexity: O(1) for
getandputsince map lookups and list manipulations take constant time. - Space Complexity: O(capacity) auxiliary space to store elements up to the cache capacity limit.
Where It Breaks
If the cache is accessed concurrently by multiple threads, the doubly linked list pointers will experience race conditions and corrupt the cache structure. Synchronized blocks or lock striping are required to make it thread-safe in production.
Common Mistakes
- Incorrect eviction key mapping: Removing the tail node from the list but forgetting to remove its corresponding entry from the hash map, leading to dangling key references.
- Null pointer exceptions on boundaries: Forgetting dummy head and tail nodes, which requires writing complex conditional checks for empty lists.