LRU Cache
Problem
Design a data structure that supports the operations get and put for a Least Recently Used (LRU) cache with a fixed capacity, where get returns the value of the key if it exists, otherwise -1, and put inserts or updates the value of the key, evicting the least recently used item if capacity is exceeded.
- 1 ≤ capacity ≤ 3000
- 0 ≤ key ≤ 10⁴
- 0 ≤ value ≤ 10⁵
- At most 2 * 10⁵ calls will be made to get and put.
Example
capacity = 2
put(1, 1)
put(2, 2)
get(1)
put(3, 3)
get(2)
put(4, 4)
get(1)
get(3)
get(4)[null, null, null, 1, null, -1, null, 3, 4]Initially, the cache is empty with capacity 2. After put(1,1) and put(2,2), the cache holds keys 1 and 2. get(1) returns 1 and marks key 1 as recently used. put(3,3) evicts key 2 (least recently used) and inserts key 3. get(2) returns -1 since key 2 was evicted. put(4,4) evicts key 1 and inserts key 4. get(1) returns -1 (evicted), get(3) returns 3, and get(4) returns 4.
Approach
Straightforward Solution
A naive approach might use a list or queue to track usage order and a hash map for values, but removing an arbitrary element from a list is O(n), making put and get operations inefficient for large caches.
Core Observation
The LRU cache requires O(1) time for both get and put operations, which demands a data structure that supports fast lookup, insertion, deletion, and ordering by recent use. A hash map provides O(1) key lookup, but does not maintain order. A doubly linked list supports O(1) insertion and removal of nodes and maintains the order of usage, enabling quick eviction of the least recently used item.
Path to Optimal
The key insight is to combine a hash map and a doubly linked list. The hash map stores keys mapped to nodes in the doubly linked list, which maintains the usage order with the most recently used at the tail and least recently used at the head. On get or put, the accessed node is moved to the tail to mark it as recently used. When capacity is exceeded, the head node is removed and its key deleted from the hash map. This design ensures all operations run in O(1).
Optimal Approach
Implement the cache with a hash map for O(1) key-to-node lookup and a doubly linked list to track usage order. Define helper methods to remove a node and insert a node at the tail. On get, if the key exists, remove the node from its current position and re-insert it at the tail, then return its value. On put, if the key exists, remove the old node, then insert the new node at the tail. If capacity is exceeded, remove the head node and delete its key from the hash map. This approach guarantees O(1) time complexity for both operations.
Time
O(1)
All operations (get, put, remove, insert) involve constant-time hash map lookups and pointer updates in the doubly linked list, ensuring O(1) time per operation.
Space
O(capacity)
The hash map and doubly linked list store at most capacity number of nodes, so space scales linearly with the cache capacity.
Pattern Spotlight
Design & Composition (Hash Map + Doubly Linked List)
Combine a hash map for fast key lookup with a doubly linked list to maintain usage order, enabling O(1) access, insertion, and eviction by moving nodes to the tail on access and removing from the head on capacity overflow.
Solution
| 1 | class Node:
|
| 2 | def __init__(self, key, val):
|
| 3 | self.key, self.val = key, val
|
| 4 | self.prev = self.next = None
|
| 5 |
|
| 6 | class LRUCache:
|
| 7 | def __init__(self, capacity: int):
|
| 8 | self.cap = capacity
|
| 9 | self.cache = {}
|
| 10 | self.left, self.right = Node(0, 0), Node(0, 0)
|
| 11 | self.left.next, self.right.prev = self.right, self.left
|
| 12 |
|
| 13 | def remove(self, node):
|
| 14 | prev, nxt = node.prev, node.next
|
| 15 | prev.next, nxt.prev = nxt, prev
|
| 16 |
|
| 17 | def insert(self, node):
|
| 18 | prev, nxt = self.right.prev, self.right
|
| 19 | prev.next = nxt.prev = node
|
| 20 | node.next, node.prev = nxt, prev
|
| 21 |
|
| 22 | def get(self, key: int) -> int:
|
| 23 | if key in self.cache:
|
| 24 | self.remove(self.cache[key])
|
| 25 | self.insert(self.cache[key])
|
| 26 | return self.cache[key].val
|
| 27 | return -1
|
| 28 |
|
| 29 | def put(self, key: int, value: int) -> None:
|
| 30 | if key in self.cache:
|
| 31 | self.remove(self.cache[key])
|
| 32 | self.cache[key] = Node(key, value)
|
| 33 | self.insert(self.cache[key])
|
| 34 |
|
| 35 | if len(self.cache) > self.cap:
|
| 36 | lru = self.left.next
|
| 37 | self.remove(lru)
|
| 38 | del self.cache[lru.key] |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | class Node { |
| 5 | int key; |
| 6 | int val; |
| 7 | Node prev; |
| 8 | Node next; |
| 9 | |
| 10 | Node(int key, int val) { |
| 11 | this.key = key; |
| 12 | this.val = val; |
| 13 | this.prev = null; |
| 14 | this.next = null; |
| 15 | } |
| 16 | } |
| 17 | |
| 18 | public class LRUCache { |
| 19 | private int cap; |
| 20 | private Map<Integer, Node> cache; |
| 21 | private Node left; |
| 22 | private Node right; |
| 23 | |
| 24 | public LRUCache(int capacity) { |
| 25 | this.cap = capacity; |
| 26 | this.cache = new HashMap<>(); |
| 27 | this.left = new Node(0, 0); |
| 28 | this.right = new Node(0, 0); |
| 29 | this.left.next = this.right; |
| 30 | this.right.prev = this.left; |
| 31 | } |
| 32 | |
| 33 | private void remove(Node node) { |
| 34 | Node prev = node.prev; |
| 35 | Node next = node.next; |
| 36 | prev.next = next; |
| 37 | next.prev = prev; |
| 38 | } |
| 39 | |
| 40 | private void insert(Node node) { |
| 41 | Node prev = this.right.prev; |
| 42 | Node next = this.right; |
| 43 | prev.next = node; |
| 44 | node.prev = prev; |
| 45 | node.next = next; |
| 46 | next.prev = node; |
| 47 | } |
| 48 | |
| 49 | public int get(int key) { |
| 50 | if (this.cache.containsKey(key)) { |
| 51 | Node node = this.cache.get(key); |
| 52 | remove(node); |
| 53 | insert(node); |
| 54 | return node.val; |
| 55 | } |
| 56 | return -1; |
| 57 | } |
| 58 | |
| 59 | public void put(int key, int value) { |
| 60 | if (this.cache.containsKey(key)) { |
| 61 | remove(this.cache.get(key)); |
| 62 | } |
| 63 | Node node = new Node(key, value); |
| 64 | this.cache.put(key, node); |
| 65 | insert(node); |
| 66 | |
| 67 | if (this.cache.size() > this.cap) { |
| 68 | Node lru = this.left.next; |
| 69 | remove(lru); |
| 70 | this.cache.remove(lru.key); |
| 71 | } |
| 72 | } |
| 73 | } |
| 1 | #include <unordered_map> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Node { |
| 6 | public: |
| 7 | int key, val; |
| 8 | Node* prev; |
| 9 | Node* next; |
| 10 | Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {} |
| 11 | }; |
| 12 | |
| 13 | class LRUCache { |
| 14 | private: |
| 15 | int cap; |
| 16 | unordered_map<int, Node*> cache; |
| 17 | Node* left; |
| 18 | Node* right; |
| 19 | |
| 20 | void remove(Node* node) { |
| 21 | Node* prev = node->prev; |
| 22 | Node* nxt = node->next; |
| 23 | prev->next = nxt; |
| 24 | nxt->prev = prev; |
| 25 | } |
| 26 | |
| 27 | void insert(Node* node) { |
| 28 | Node* prev = right->prev; |
| 29 | Node* nxt = right; |
| 30 | prev->next = node; |
| 31 | node->prev = prev; |
| 32 | node->next = nxt; |
| 33 | nxt->prev = node; |
| 34 | } |
| 35 | |
| 36 | public: |
| 37 | LRUCache(int capacity) : cap(capacity) { |
| 38 | left = new Node(0, 0); |
| 39 | right = new Node(0, 0); |
| 40 | left->next = right; |
| 41 | right->prev = left; |
| 42 | } |
| 43 | |
| 44 | int get(int key) { |
| 45 | if (cache.find(key) != cache.end()) { |
| 46 | Node* node = cache[key]; |
| 47 | remove(node); |
| 48 | insert(node); |
| 49 | return node->val; |
| 50 | } |
| 51 | return -1; |
| 52 | } |
| 53 | |
| 54 | void put(int key, int value) { |
| 55 | if (cache.find(key) != cache.end()) { |
| 56 | remove(cache[key]); |
| 57 | delete cache[key]; |
| 58 | } |
| 59 | Node* node = new Node(key, value); |
| 60 | cache[key] = node; |
| 61 | insert(node); |
| 62 | |
| 63 | if ((int)cache.size() > cap) { |
| 64 | Node* lru = left->next; |
| 65 | remove(lru); |
| 66 | cache.erase(lru->key); |
| 67 | delete lru; |
| 68 | } |
| 69 | } |
| 70 | |
| 71 | ~LRUCache() { |
| 72 | Node* current = left; |
| 73 | while (current != nullptr) { |
| 74 | Node* next = current->next; |
| 75 | delete current; |
| 76 | current = next; |
| 77 | } |
| 78 | } |
| 79 | }; |
| 1 | class Node { |
| 2 | constructor(key, val) { |
| 3 | this.key = key; |
| 4 | this.val = val; |
| 5 | this.prev = null; |
| 6 | this.next = null; |
| 7 | } |
| 8 | } |
| 9 | |
| 10 | class LRUCache { |
| 11 | constructor(capacity) { |
| 12 | this.cap = capacity; |
| 13 | this.cache = new Map(); |
| 14 | this.left = new Node(0, 0); |
| 15 | this.right = new Node(0, 0); |
| 16 | this.left.next = this.right; |
| 17 | this.right.prev = this.left; |
| 18 | } |
| 19 | |
| 20 | remove(node) { |
| 21 | let prev = node.prev; |
| 22 | let next = node.next; |
| 23 | prev.next = next; |
| 24 | next.prev = prev; |
| 25 | } |
| 26 | |
| 27 | insert(node) { |
| 28 | let prev = this.right.prev; |
| 29 | let next = this.right; |
| 30 | prev.next = node; |
| 31 | node.prev = prev; |
| 32 | node.next = next; |
| 33 | next.prev = node; |
| 34 | } |
| 35 | |
| 36 | get(key) { |
| 37 | if (this.cache.has(key)) { |
| 38 | let node = this.cache.get(key); |
| 39 | this.remove(node); |
| 40 | this.insert(node); |
| 41 | return node.val; |
| 42 | } |
| 43 | return -1; |
| 44 | } |
| 45 | |
| 46 | put(key, value) { |
| 47 | if (this.cache.has(key)) { |
| 48 | this.remove(this.cache.get(key)); |
| 49 | } |
| 50 | let node = new Node(key, value); |
| 51 | this.cache.set(key, node); |
| 52 | this.insert(node); |
| 53 | |
| 54 | if (this.cache.size > this.cap) { |
| 55 | let lru = this.left.next; |
| 56 | this.remove(lru); |
| 57 | this.cache.delete(lru.key); |
| 58 | } |
| 59 | } |
| 60 | } |
Step-by-Step Solution
Define Node Structure for Doubly Linked List Entries
| 3 | self.key, self.val = key, val
|
| 4 | self.prev = self.next = None
|
Objective
To represent each cache entry as a doubly linked list node storing its key, value, and neighbor pointers.
Key Insight
The cache map points to nodes, not raw values. Each node must therefore carry its key for O(1) eviction cleanup and its prev/next links for O(1) removal and insertion.
Interview Quick-Check
Core Logic
Each cache entry needs both payload fields and doubly linked list pointers so it can move in O(1).
Common Pitfalls & Bugs
If the node does not store its key, eviction cannot remove the matching map entry in O(1).
Initialize Cache State with Dummy Head and Tail Nodes
| 8 | self.cap = capacity
|
| 9 | self.cache = {}
|
| 10 | self.left, self.right = Node(0, 0), Node(0, 0)
|
| 11 | self.left.next, self.right.prev = self.right, self.left
|
Objective
To set up the cache capacity, hash map, and doubly linked list with sentinel nodes to simplify insertion and removal operations.
Key Insight
Using dummy head and tail nodes avoids edge cases when inserting or removing nodes at the boundaries of the doubly linked list. The hash map stores key-node pairs for O(1) lookup. This initialization creates a clean, consistent structure that supports efficient updates.
Interview Quick-Check
Core Logic
Dummy head and tail nodes simplify linked list operations by eliminating null checks and special cases for empty or single-element lists.
State & Boundaries
The cache capacity is fixed at initialization and the hash map starts empty.
Common Pitfalls & Bugs
Forgetting to link dummy head and tail nodes correctly can cause insertion/removal bugs.
Remove a Node from the Doubly Linked List
| 14 | prev, nxt = node.prev, node.next
|
| 15 | prev.next, nxt.prev = nxt, prev
|
Objective
To unlink a node from its current position in the doubly linked list in O(1) time.
Key Insight
Removing a node requires updating the previous node's next pointer and the next node's previous pointer to bypass the node. This operation is O(1) because the node has direct references to its neighbors, enabling quick removal without traversal.
Interview Quick-Check
Core Logic
Directly updating the pointers of adjacent nodes removes the target node from the list in constant time.
Common Pitfalls & Bugs
Failing to update both prev.next and next.prev pointers leads to corrupted list structure.
Insert a Node at the Tail to Mark as Most Recently Used
| 18 | prev, nxt = self.right.prev, self.right
|
| 19 | prev.next = nxt.prev = node
|
| 20 | node.next, node.prev = nxt, prev
|
Objective
To insert a node right before the dummy tail node, marking it as the most recently used item.
Key Insight
Inserting at the tail maintains the order of usage with the most recently used nodes at the end. This involves updating the previous tail's next pointer and the tail's previous pointer to include the new node, all in O(1) time.
Interview Quick-Check
Core Logic
Inserting before the dummy tail node ensures the node is the most recently used, preserving LRU order.
Common Pitfalls & Bugs
Incorrect pointer assignments can break the list or cause cycles.
Retrieve Value and Update Usage on Get Operation
| 23 | if key in self.cache:
|
| 24 | self.remove(self.cache[key])
|
| 25 | self.insert(self.cache[key])
|
| 26 | return self.cache[key].val
|
| 27 | return -1
|
Objective
To return the value associated with a key if it exists and update its position to the most recently used.
Key Insight
Accessing a key requires moving its node to the tail to mark it as recently used. This involves removing the node from its current position and reinserting it at the tail. If the key is not found, return -1. This maintains the correct LRU order after every access.
Interview Quick-Check
Core Logic
Moving the accessed node to the tail updates its usage status, ensuring the cache correctly tracks recency.
State & Boundaries
Return -1 immediately if the key is not present in the cache.
Common Pitfalls & Bugs
Failing to move the node on get leads to incorrect eviction order.
Insert or Update Key-Value Pair and Evict if Necessary on Put
| 30 | if key in self.cache:
|
| 31 | self.remove(self.cache[key])
|
| 32 | self.cache[key] = Node(key, value)
|
| 33 | self.insert(self.cache[key])
|
| 35 | if len(self.cache) > self.cap:
|
| 36 | lru = self.left.next
|
| 37 | self.remove(lru)
|
| 38 | del self.cache[lru.key] |
Objective
To insert a new key-value pair or update an existing one, move it to the most recently used position, and evict the least recently used item if capacity is exceeded.
Key Insight
If the key exists, remove its old node before inserting the updated node at the tail. If the cache size exceeds capacity, remove the head's next node (the least recently used) and delete its key from the hash map. This maintains the cache size and usage order efficiently.
Interview Quick-Check
Core Logic
Evicting the least recently used node from the head and deleting its key maintains the cache size within capacity.
State & Boundaries
Check cache size after insertion to decide if eviction is needed.
Common Pitfalls & Bugs
Forgetting to remove the old node when updating a key causes duplicate nodes and corrupts usage order.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
prev.next, nxt.prev = nxt, prevUpdate pointers to bypass the target node, removing it from the list.
This pointer update is the critical operation that removes a node in constant time, enabling efficient cache updates without list traversal.
self.cache = {}Initialize the hash map to store key-node mappings.
The hash map enables O(1) lookup of nodes by key, which is essential for efficient get and put operations.
prev.next = nxt.prev = nodeLink the previous node and dummy tail to the new node.
This dual pointer assignment is essential to correctly insert the node at the tail, ensuring the list remains well-formed and the node is recognized as most recently used.
self.remove(self.cache[key])Remove the node associated with the key from its current position.
This removal is critical to avoid duplicate nodes and to update the node's position to most recently used, preserving the LRU semantics.
self.remove(self.cache[key])Remove the existing node for the key if present.
This removal is essential to maintain correct usage order and avoid stale nodes when updating values.
self.remove(lru)Remove the least recently used node from the doubly linked list.
This removal is the key eviction step that ensures the cache does not exceed capacity while preserving LRU order.
self.prev = self.next = NoneInitialize the node's previous and next pointers.
Initializing prev and next to None creates a detached node that can later be inserted safely into the doubly linked list.
self.left, self.right = Node(0, 0), Node(0, 0)Create dummy head and tail nodes for the doubly linked list.
Dummy nodes simplify insertion and removal by eliminating edge cases at the boundaries of the list.
node.next, node.prev = nxt, prevSet the new node's next and previous pointers to link it into the list.
Completing the bidirectional links integrates the new node fully into the doubly linked list.
self.insert(self.cache[key])Insert the node at the tail to mark it as most recently used.
Reinserting at the tail updates the usage order to reflect recent access.
self.cache[key] = Node(key, value)Create a new node with the key and value and store it in the hash map.
Storing the new node in the hash map enables O(1) lookup and associates the key with its node.
self.insert(self.cache[key])Insert the new node at the tail to mark it as most recently used.
Inserting at the tail updates the usage order to reflect the most recent insertion or update.
lru = self.left.nextIdentify the least recently used node (the node after the dummy head).
The node immediately after the dummy head is the least recently used and candidate for eviction.
del self.cache[lru.key]Delete the evicted node's key from the hash map.
Removing the key from the hash map completes the eviction, preventing stale references and enabling correct future lookups.
self.key, self.val = key, valStore the entry key and value inside the node.
Each cache entry must store its key and value together so the list node can serve as the payload referenced by the hash map and used during eviction.
self.left.next, self.right.prev = self.right, self.leftLink dummy head and tail nodes to each other.
Establishing the initial empty list structure ensures that insertions and removals can be performed uniformly.
prev, nxt = node.prev, node.nextRetrieve the previous and next nodes of the target node.
Accessing adjacent nodes is necessary to unlink the target node from the list in O(1) time.
prev, nxt = self.right.prev, self.rightIdentify the node currently before the dummy tail and the dummy tail itself.
These pointers define the insertion point for the new node to mark it as most recently used.
if key in self.cache:Check if the key exists in the cache.
Determining presence allows the algorithm to update usage order and value correctly.
if key in self.cache:Check if the key already exists in the cache.
This check determines whether to update an existing node or insert a new one.
if len(self.cache) > self.cap:Check if the cache size exceeds its capacity.
This condition triggers eviction of the least recently used item to maintain capacity constraints.
self.cap = capacityStore the cache capacity.
The capacity defines the maximum number of items the cache can hold, which is critical for eviction logic.
return self.cache[key].valReturn the value associated with the key.
Returning the stored value fulfills the get operation's contract.
return -1Return -1 if the key is not found in the cache.
Indicating absence with -1 is required by the problem specification.
Test Your Understanding
Why does combining a hash map with a doubly linked list enable O(1) time complexity for both get and put operations in an LRU cache?
The hash map provides O(1) access to nodes by key, while the doubly linked list maintains the order of usage and supports O(1) insertion and removal of nodes. Together, they allow quick updates to usage order and efficient eviction of the least recently used item.
Don't just read it. Drill it.
Reconstruct LRU Cache from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the LRU Cache drill