Appearance
4.9.9 — LRU Cache
LeetCode 146 · Medium · ★ Blind 75
The problem
Design a cache with a fixed capacity. A cache is a small, fast store that keeps recently used data close at hand, so you do not have to fetch it from somewhere slow again. This one must support two operations, both in O(1) time.
get(key)returns the value stored forkey, or −1 if the key is not there. Reading a key counts as using it.put(key, value)stores the value. If the key already exists, its value is updated. If storing it makes the cache hold more thancapacitykeys, throw out the least recently used key. That is what LRU stands for.
LRUCache(2) capacity 2
put(1, 1) cache: {1}
put(2, 2) cache: {1, 2}
get(1) → 1 1 is now the most recently used
put(3, 3) too many keys: throw out 2, the least recently used
get(2) → -1 2 is gone
get(3) → 3The capacity is up to 3,000, and there are up to 200,000 calls.
What the problem is really asking
Think of browser tabs, with room for only a few. When you open a new tab and you are at the limit, the browser closes the tab you have not looked at for the longest time. When you click an old tab, it becomes the most recently used again.
Two jobs pull in different directions.
- Find a key instantly. That is what a hash map does. But a hash map has no idea which key was used longest ago.
- Keep the keys in order of use, and move any key to the "most recent" end instantly. An ordered list does that. But finding a key in a list means walking it.
So the real question is: how do you get instant lookup and instant reordering at the same time?
The brute force, and where it wastes work
Keep a list of keys in order of use, most recent first, alongside a map of values. On get, find the key in the list, remove it, and put it at the front.
Finding a key in a list, and removing it from the middle, both take O(n), because the items after it have to shift along. With 200,000 calls and a capacity of 3,000, that is hundreds of millions of steps.
The waste in one sentence: every use shifts a list to move one key, when a linked list could unhook that key and re-hook it at the front by changing four pointers.
The idea
Use both structures, and let each cover the other's weakness.
- A hash map from each key to a node. This gives O(1) lookup.
- A doubly linked list of those nodes, in order of use: most recent at the front, least recent at the back. This gives O(1) reordering.
The map finds the node. The list knows the order. Saying this in one sentence is the whole point of the problem.
Read the figure in two parts. On the left, the hash map turns a key into a node in one step. On the right, the nodes sit in order of use, with the most recent nearest the head and the least recent nearest the tail. The head and tail boxes are fake nodes that never hold data. To use key 1, the map jumps straight to node 1, which is then unhooked and re-hooked just after head. To make room, we remove whatever sits just before tail.
Why the list must be doubly linked
To move a node to the front, you must first unhook it from where it is. To unhook a node, you need the node before it, so you can point that node past it.
In a singly linked list, finding the node before costs O(n), because you must walk from the head. If every node also has a prev pointer, the node before is one step away. That is the entire reason for the second pointer.
Why two dummy nodes
Adding at the front and removing at the back both have awkward cases: an empty list, a list of one, a node at the very edge. They all disappear if there are permanent fake nodes at both ends. Then every real node has a real neighbour on each side, and unhooking is always the same two lines with no ifs. This is the dummy-head idea from 4.9.2, used at both ends.
The solution
python
class Node:
def __init__(self, key=0, val=0):
self.key, self.val = key, val # (1)
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {} # (2)
self.head = Node() # (3)
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node): # (4)
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node): # (5)
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.map: # (6)
return -1
node = self.map[key]
self._remove(node) # (7)
self._add_front(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.map: # (8)
self._remove(self.map[key])
node = Node(key, value) # (9)
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap: # (10)
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key] # (11)ts
class LNode {
key = 0; val = 0; // (1)
prev: LNode | null = null;
next: LNode | null = null;
constructor(key = 0, val = 0) { this.key = key; this.val = val; }
}
class LRUCache {
private cap: number;
private map = new Map<number, LNode>(); // (2)
private head = new LNode(); // (3)
private tail = new LNode();
constructor(capacity: number) {
this.cap = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
private remove(node: LNode) { // (4)
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
private addFront(node: LNode) { // (5)
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
}
get(key: number): number {
const node = this.map.get(key);
if (!node) return -1; // (6)
this.remove(node); // (7)
this.addFront(node);
return node.val;
}
put(key: number, value: number): void {
const existing = this.map.get(key);
if (existing) this.remove(existing); // (8)
const node = new LNode(key, value); // (9)
this.map.set(key, node);
this.addFront(node);
if (this.map.size > this.cap) { // (10)
const lru = this.tail.prev!;
this.remove(lru);
this.map.delete(lru.key); // (11)
}
}
}Line by line
(1) Each node stores its key as well as its value. This looks like a waste, but line (11) needs it. Hold that thought.
(2) The map from key to node.
(3) The two dummy nodes, linked to each other. The list starts out as head ⇄ tail, with nothing real in between.
(4) Unhook a node. Point the node before it at the node after it, and the node after it back at the node before it. The node is now out of the chain. Thanks to the dummies, node.prev and node.next always exist, so there is no if.
(5) Hook a node in just after head. Four pointer changes, in this order:
- The new node's
nextis the current first real node (ortailif the list is empty). - The new node's
previshead. - The current first node points back at the new node.
headpoints forward to the new node.
Order matters here. Steps 1 and 3 both read self.head.next, so step 4, which overwrites it, must come last.
(6) A key that is not there returns −1.
(7) Reading counts as using. Unhook the node and hook it back in at the front. If you forget this, you get a "least recently added" cache, which passes some tests and fails the ones that matter.
(8) Updating an existing key. Unhook its old node. A new node with the new value takes its place in the next line. (You could instead change the old node's value and move it to the front. That works just as well and creates one fewer object.)
(9) Create the node, record it in the map, and hook it in at the front.
(10) Too many keys? The least recently used node is always the one just before tail. Unhook it.
(11) Remove it from the map too, using its key. This is why line (1) stores the key. We found the node through the list, not the map. To delete its map entry, we need its key. Without the key stored on the node, we would have to search the whole map for it, which is O(n) and ruins the design. This is the detail most people miss.
Trace
Capacity 2. The list is shown front to back, without the dummies.
| Call | Map keys after | List after (most recent first) | Returns |
|---|---|---|---|
| put(1, 1) | 1 | — | |
| put(2, 2) | 2, 1 | — | |
| get(1) | 1, 2 (1 moved to front) | 1 | |
| put(3, 3) | {1, 2, 3} → too many → remove 2 → | 3, 1 | — |
| get(2) | 3, 1 | −1 | |
| get(3) | 3, 1 | 3 |
At put(3, 3), the node just before tail was 2, so 2 was thrown out. Without the get(1) step, it would have been 1.
Complexity, derived
Time. Every operation is a few map operations, each O(1) on average, plus calls to _remove and _add_front, which change a fixed number of pointers with no loops. So get and put are both O(1).
Space. The map holds at most capacity entries, and the list holds at most capacity real nodes plus two dummies. So the space is O(\text{capacity}).
Edge cases
- Capacity 1. Every new key throws out the previous one. The dummies make this work with no special case.
puton an existing key. It moves to the front with its new value, and nothing is thrown out, because the number of keys does not change.geton a missing key. Returns −1 and changes nothing.- Many
gets of the same key. It stays at the front.
The shortcut, and why to know both
Python has OrderedDict, a hash map that remembers the order keys were added and can move a key to either end in O(1).
python
from collections import OrderedDict
class LRUCache(OrderedDict):
def __init__(self, capacity):
self.cap = capacity
def get(self, key):
if key not in self:
return -1
self.move_to_end(key) # mark as most recent
return self[key]
def put(self, key, value):
if key in self:
self.move_to_end(key)
self[key] = value
if len(self) > self.cap:
self.popitem(last=False) # remove the oldest keyJavaScript's Map also remembers insertion order. Deleting a key and setting it again moves it to the end, and map.keys().next().value gives the oldest key.
Both are correct, and both are how you would write it in real code. In an interview, write the manual version. The question is testing whether you can build the structure. OrderedDict is, inside, a hash map plus a doubly linked list doing exactly what you would have built. Say that, then offer the shortcut.
Variations you will meet
- LFU Cache. Throw out the least frequently used key instead. You need a map from each use-count to a list of keys with that count, plus the current lowest count. It is much harder, and it is the natural follow-up. See 4.9.12.
- Real caches. Database memory, your processor's cache and your browser's cache all face this choice. Many do not keep a true LRU order, because updating pointers on every single read is costly when many requests arrive at once. They use cheaper approximations instead.
The general lesson: when one structure cannot give you both fast lookup and a useful order, combine two and keep them in step.
What the interviewer will push on
"Why a doubly linked list?" Unhooking a node needs the node before it, and only a prev pointer gives that in O(1).
"Why does each node store its key?" To delete its map entry when it is thrown out.
"Does get change the order?" Yes. Reading is using.
"How would you make it safe for many threads?" The map and the list must always agree, so every operation must hold one lock around both changes. If another thread could see a node in the map that had already left the list, it would read broken data.
One thing to volunteer: state the design in one sentence before writing anything. "A hash map for O(1) lookup, a doubly linked list for O(1) reordering, and the map points at the list's nodes." Then build it.
Next: 4.9.10 Merge K Sorted Lists. The merge from 4.9.2, scaled up, and the first appearance of a heap.