LRU Cache (LeetCode 146)
A cache with a fixed capacity needs to hold key-value pairs and, whenever it's full and a new key arrives, evict whichever key was touched longest ago.
Build an LRUCache class:
LRUCache(int capacity)sets up the cache with a positivecapacity.int get(int key)returns the value stored forkey, or-1ifkeyisn't present.void put(int key, int value)insertskeywithvalue, or overwrites the value ifkeyis already present. If this push takes the cache pastcapacity, evict the least recently used key first.
Both get and put must run in O(1) average time.
Worked Examples
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]][null, null, null, 1, null, -1, null, -1, 3, 4]⚖️Formal Constraints & Bounds
1 <= capacity <= 30000 <= key <= 1040 <= value <= 105At most 2 * 105 calls will be made to get and put.
Core Insight
Pair a Hash Map for O(1) key lookups with a Doubly-Linked List for O(1) node splicing. Moving accessed nodes to head.next guarantees MRU order; removing tail.prev evicts LRU.
Real-World Scenario & Production Applications
Page replacement algorithms in operating systems, Redis in-memory cache eviction policies, CDN edge caching.
Subproblems & Recurrence Decomposition3 Phases
A hash map gives O(1) key lookup; a doubly linked list gives O(1) reordering. Every cache entry lives in both: the map points directly to its list node.
self.cache = {} # key -> DLinkedNode
self.head, self.tail = DLinkedNode(), DLinkedNode() # sentinels
self.head.next, self.tail.prev = self.tail, self.headStep-by-Step Execution Trace Table
| Step | Operation | Hash Map Keys | Doubly-Linked List (MRU LRU) | Evicted Key | Return Value |
|---|---|---|---|---|---|
| 1 | LRUCache(2) | {} | [Head] <-> [Tail] | - | null |
| 2 | put(1, 1) | {1: Node(1,1)} | [Head] <-> [1:1] <-> [Tail] | - | null |
| 3 | put(2, 2) | {1, 2} | [Head] <-> [2:2] <-> [1:1] <-> [Tail] | - | null |
| 4 | get(1) | {1, 2} | [Head] <-> [1:1] <-> [2:2] <-> [Tail] | - | 1 (promoted to MRU) |
| 5 | put(3, 3) | {1, 3} | [Head] <-> [3:3] <-> [1:1] <-> [Tail] | 2 (Tail.prev) | null (evicted key 2) |
| 6 | get(2) | {1, 3} | [Head] <-> [3:3] <-> [1:1] <-> [Tail] | - | -1 (cache miss) |
| 7 | put(4, 4) | {3, 4} | [Head] <-> [4:4] <-> [3:3] <-> [Tail] | 1 (Tail.prev) | null (evicted key 1) |
| 8 | get(1) | {3, 4} | [Head] <-> [4:4] <-> [3:3] <-> [Tail] | - | -1 (cache miss) |
| 1 | self.cache = {} # key -> DLinkedNode |
| 2 | head <-> [MRU ... LRU] <-> tail |
| 3 | get(key) -> _remove(node), _add_to_head(node) |
| 4 | put(key, value) -> existing key: update node.val, then move it to head |
| 5 | put(key, value) -> new key: if full, _remove(tail.prev) and del self.cache[lru.key], then _add_to_head(new_node) |
Conceptual Narrative
Neither a hash map nor a linked list alone can implement LRU in O(1): a hash map lacks temporal order, while a linked list lacks O(1) random access. Combining them achieves strict O(1) get and put operations.
🧭 Conceptual Foundation & Pattern Intuition
A Least Recently Used (LRU) Cache requires two capabilities:
- Value Retrieval: Look up the cached value for any key in constant time.
- Recency Promotion & Eviction: Moving an accessed item to the "most recently used" position and evicting the "least recently used" item when capacity is exceeded must both run in time. A hash map alone provides lookups, but tracking eviction order requires an array with shift costs. A singly linked list maintains order, but removing a node from the middle requires scanning to find the predecessor. The solution is a Hash Map paired with a Doubly-Linked List (DLL):
- The hash map stores
key -> Node, providing direct access to any node in memory. - The Doubly-Linked List has
prevandnextpointers on every node, enabling unlinking from the middle:node.prev.next = node.next; node.next.prev = node.prev. - Pseudo-sentinel nodes (
headandtail) permanently enclose the list, eliminating edge-case null checks during head insertion and tail eviction.
🃏 The Analogy: A Card Rack with Direct Storage Slots
Imagine a retail display rack of gift cards laid out horizontally from left (Most Recently Touched) to right (Least Recently Touched). Above the rack is a computerized inventory directory. When a customer asks for card "X", the computer immediately pinpoints card X's physical slot in the rack. The clerk grabs card X, snaps the gap shut in one click (linking the left and right neighbors), and drops card X at the far left of the rack. When a new shipment arrives and the rack is full, the clerk simply discards the card resting at the far right end—no searching required.
🔑 Why It Works
Sentinels turn node splicing into an unconditional 4-pointer assignment without a single if node.prev is None conditional, delivering rock-solid, production-grade speed.
Using a singly-linked list: Node removal requires access to the previous node, which takes
O(N)without a back-pointer; a doubly-linked list with dummy head and tail is mandatory for trueO(1)detachment and promotion.Stale Hash Map References: Forgetting to delete evicted node from hash map cache when capacity is exceeded leaves stale keys and causes capacity checks to fail.
Reading existing key via
get()without moving node to MRU: In LRU, accessing a key viaget()marks it as most recently used. Failing to detach and move the node to the head of the list causes active keys to be evicted prematurely.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Key-value cache with capacity bound + O(1) get and put + eviction of least recently used item.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: Hash map gives O(1) pointer to doubly-linked list node; DLL node removal and head insertion require only pointer reassignment without array shifts.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
puton an existing key must setnode.val = valueand move the node to the front, or it keeps its old place and is evicted too early.On eviction, remove
self.tail.prevfrom the list anddel self.cache[lru.key]; forgetting the map entry leaves a key that points at an evicted node.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd build the LRU Cache from a hash map and a doubly-linked list with dummy head and tail nodes. The map takes a key to its node in
O(1); the list keeps nodes in order of use, most recent next to head. Every get and every put moves its node next to head, so the node just before tail is always the least recently used. When a new key arrives and the cache is full, I remove that node and delete its key from the map, which is why each node stores its key. The trap is put on a key that is already there: I update the value and move the node to the front too, or it keeps its old place and is evicted too early. Every call isO(1), and the space is O(capacity)."
Complexity & Mathematical Proof
O(1) get and put
Look at both get(key) and put(key, value) operations: The hash map provides O(1) average pointer lookup to any node in the cache. Splicing a node out of the doubly-linked list (_remove) updates 2 pointer references in O(1) constant time. Inserting at head (_add_to_head) updates 4 pointer references in O(1) constant time. Evicting the tail (tail.prev) is also O(1). Every operation runs in strictly O(1) average time.
O(capacity)
Look at memory allocation: The cache holds at most capacity entries. The hash map stores capacity key-node pairs, and the DLL contains capacity + 2 nodes (two sentinels). Total space is O(capacity).
Derivation Progression
Hash table locates the memory pointer for any existing key in constant average time.
Re-linking node.prev.next = node.next and node.next.prev = node.prev removes a node without array shifts.
Adding behind dummy head marks Most Recently Used; popping before dummy tail removes Least Recently Used.
Variable Definitions
Maximum number of keys the cache holds
Total number of get and put operations performed
Memory Architecture & Bounds
O(1) Non-recursive method calls
O(capacity): hash map of up to capacity keys + doubly linked list of up to capacity nodes
O(1) Scalar return values
Boundary Best / Worst Cases
for both get and put operations.
standard hash table distribution.
average ( only if every key collides in the hash map).
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "evict the least recently used key", "O(1) average time". The dual requirement of key lookup and eviction ordering uniquely points to a Hash Map + Doubly Linked List with Sentinel Head/Tail.
Capacity , up to operations. Strictly amortized runtime per operation.
Concurrency: get changes the list, so even reads need a lock (or a sharded cache, one lock per shard), and a lock around every read can become the bottleneck under heavy traffic. Memory: each entry costs a node with two pointers plus a map slot, so a cache measured in bytes, not entries, must evict until the total size fits.
LRU Cache (LeetCode 146)
A cache with a fixed capacity needs to hold key-value pairs and, whenever it's full and a new key arrives, evict whichever key was touched longest ago.
Build an LRUCache class:
LRUCache(int capacity)sets up the cache with a positivecapacity.int get(int key)returns the value stored forkey, or-1ifkeyisn't present.void put(int key, int value)insertskeywithvalue, or overwrites the value ifkeyis already present. If this push takes the cache pastcapacity, evict the least recently used key first.
Both get and put must run in O(1) average time.
Worked Examples
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]][null, null, null, 1, null, -1, null, -1, 3, 4]⚖️Formal Constraints & Bounds
1 <= capacity <= 30000 <= key <= 1040 <= value <= 105At most 2 * 105 calls will be made to get and put.
Core Insight
Pair a Hash Map for O(1) key lookups with a Doubly-Linked List for O(1) node splicing. Moving accessed nodes to head.next guarantees MRU order; removing tail.prev evicts LRU.
Real-World Scenario & Production Applications
Page replacement algorithms in operating systems, Redis in-memory cache eviction policies, CDN edge caching.
Subproblems & Recurrence Decomposition3 Phases
A hash map gives O(1) key lookup; a doubly linked list gives O(1) reordering. Every cache entry lives in both: the map points directly to its list node.
self.cache = {} # key -> DLinkedNode
self.head, self.tail = DLinkedNode(), DLinkedNode() # sentinels
self.head.next, self.tail.prev = self.tail, self.headStep-by-Step Execution Trace Table
| Step | Operation | Hash Map Keys | Doubly-Linked List (MRU LRU) | Evicted Key | Return Value |
|---|---|---|---|---|---|
| 1 | LRUCache(2) | {} | [Head] <-> [Tail] | - | null |
| 2 | put(1, 1) | {1: Node(1,1)} | [Head] <-> [1:1] <-> [Tail] | - | null |
| 3 | put(2, 2) | {1, 2} | [Head] <-> [2:2] <-> [1:1] <-> [Tail] | - | null |
| 4 | get(1) | {1, 2} | [Head] <-> [1:1] <-> [2:2] <-> [Tail] | - | 1 (promoted to MRU) |
| 5 | put(3, 3) | {1, 3} | [Head] <-> [3:3] <-> [1:1] <-> [Tail] | 2 (Tail.prev) | null (evicted key 2) |
| 6 | get(2) | {1, 3} | [Head] <-> [3:3] <-> [1:1] <-> [Tail] | - | -1 (cache miss) |
| 7 | put(4, 4) | {3, 4} | [Head] <-> [4:4] <-> [3:3] <-> [Tail] | 1 (Tail.prev) | null (evicted key 1) |
| 8 | get(1) | {3, 4} | [Head] <-> [4:4] <-> [3:3] <-> [Tail] | - | -1 (cache miss) |
| 1 | self.cache = {} # key -> DLinkedNode |
| 2 | head <-> [MRU ... LRU] <-> tail |
| 3 | get(key) -> _remove(node), _add_to_head(node) |
| 4 | put(key, value) -> existing key: update node.val, then move it to head |
| 5 | put(key, value) -> new key: if full, _remove(tail.prev) and del self.cache[lru.key], then _add_to_head(new_node) |
Conceptual Narrative
Neither a hash map nor a linked list alone can implement LRU in O(1): a hash map lacks temporal order, while a linked list lacks O(1) random access. Combining them achieves strict O(1) get and put operations.
🧭 Conceptual Foundation & Pattern Intuition
A Least Recently Used (LRU) Cache requires two capabilities:
- Value Retrieval: Look up the cached value for any key in constant time.
- Recency Promotion & Eviction: Moving an accessed item to the "most recently used" position and evicting the "least recently used" item when capacity is exceeded must both run in time. A hash map alone provides lookups, but tracking eviction order requires an array with shift costs. A singly linked list maintains order, but removing a node from the middle requires scanning to find the predecessor. The solution is a Hash Map paired with a Doubly-Linked List (DLL):
- The hash map stores
key -> Node, providing direct access to any node in memory. - The Doubly-Linked List has
prevandnextpointers on every node, enabling unlinking from the middle:node.prev.next = node.next; node.next.prev = node.prev. - Pseudo-sentinel nodes (
headandtail) permanently enclose the list, eliminating edge-case null checks during head insertion and tail eviction.
🃏 The Analogy: A Card Rack with Direct Storage Slots
Imagine a retail display rack of gift cards laid out horizontally from left (Most Recently Touched) to right (Least Recently Touched). Above the rack is a computerized inventory directory. When a customer asks for card "X", the computer immediately pinpoints card X's physical slot in the rack. The clerk grabs card X, snaps the gap shut in one click (linking the left and right neighbors), and drops card X at the far left of the rack. When a new shipment arrives and the rack is full, the clerk simply discards the card resting at the far right end—no searching required.
🔑 Why It Works
Sentinels turn node splicing into an unconditional 4-pointer assignment without a single if node.prev is None conditional, delivering rock-solid, production-grade speed.
Using a singly-linked list: Node removal requires access to the previous node, which takes
O(N)without a back-pointer; a doubly-linked list with dummy head and tail is mandatory for trueO(1)detachment and promotion.Stale Hash Map References: Forgetting to delete evicted node from hash map cache when capacity is exceeded leaves stale keys and causes capacity checks to fail.
Reading existing key via
get()without moving node to MRU: In LRU, accessing a key viaget()marks it as most recently used. Failing to detach and move the node to the head of the list causes active keys to be evicted prematurely.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Key-value cache with capacity bound + O(1) get and put + eviction of least recently used item.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: Hash map gives O(1) pointer to doubly-linked list node; DLL node removal and head insertion require only pointer reassignment without array shifts.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
puton an existing key must setnode.val = valueand move the node to the front, or it keeps its old place and is evicted too early.On eviction, remove
self.tail.prevfrom the list anddel self.cache[lru.key]; forgetting the map entry leaves a key that points at an evicted node.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd build the LRU Cache from a hash map and a doubly-linked list with dummy head and tail nodes. The map takes a key to its node in
O(1); the list keeps nodes in order of use, most recent next to head. Every get and every put moves its node next to head, so the node just before tail is always the least recently used. When a new key arrives and the cache is full, I remove that node and delete its key from the map, which is why each node stores its key. The trap is put on a key that is already there: I update the value and move the node to the front too, or it keeps its old place and is evicted too early. Every call isO(1), and the space is O(capacity)."
Complexity & Mathematical Proof
O(1) get and put
Look at both get(key) and put(key, value) operations: The hash map provides O(1) average pointer lookup to any node in the cache. Splicing a node out of the doubly-linked list (_remove) updates 2 pointer references in O(1) constant time. Inserting at head (_add_to_head) updates 4 pointer references in O(1) constant time. Evicting the tail (tail.prev) is also O(1). Every operation runs in strictly O(1) average time.
O(capacity)
Look at memory allocation: The cache holds at most capacity entries. The hash map stores capacity key-node pairs, and the DLL contains capacity + 2 nodes (two sentinels). Total space is O(capacity).
Derivation Progression
Hash table locates the memory pointer for any existing key in constant average time.
Re-linking node.prev.next = node.next and node.next.prev = node.prev removes a node without array shifts.
Adding behind dummy head marks Most Recently Used; popping before dummy tail removes Least Recently Used.
Variable Definitions
Maximum number of keys the cache holds
Total number of get and put operations performed
Memory Architecture & Bounds
O(1) Non-recursive method calls
O(capacity): hash map of up to capacity keys + doubly linked list of up to capacity nodes
O(1) Scalar return values
Boundary Best / Worst Cases
for both get and put operations.
standard hash table distribution.
average ( only if every key collides in the hash map).
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "evict the least recently used key", "O(1) average time". The dual requirement of key lookup and eviction ordering uniquely points to a Hash Map + Doubly Linked List with Sentinel Head/Tail.
Capacity , up to operations. Strictly amortized runtime per operation.
Concurrency: get changes the list, so even reads need a lock (or a sharded cache, one lock per shard), and a lock around every read can become the bottleneck under heavy traffic. Memory: each entry costs a node with two pointers plus a map slot, so a cache measured in bytes, not entries, must evict until the total size fits.