-
Notifications
You must be signed in to change notification settings - Fork 0
073 — LRU Cache
LeetCode 146 · Medium. Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement LRUCache(_ capacity: Int), get(_ key: Int) -> Int (returns the value or -1 if not present, and marks the key as recently used), and put(_ key: Int, _ value: Int) (inserts or updates the value; if the cache is at capacity, evicts the least recently used key first before inserting). Both operations must run in O(1) average time.
Picture a small stack of books on your desk, arranged left to right — every time you pull a book out to read it, you set it back down at the front of the stack, not wherever it came from. Books you haven't touched in a while naturally drift toward the back. When the desk is full and a new book arrives, you don't need to think hard about which one to remove — it's whatever is sitting at the very back, because by construction that's the one you touched longest ago. The trick is doing "pull this book out and put it at the front" instantly, no matter where in the stack it currently sits — which a plain array-like stack can't do without shifting everything.
"Design a cache" plus "least recently used" plus O(1) get/put is a data-structure-design signature, not a search-and-compute one. Whenever a problem needs O(1) lookup by key and O(1) reordering based on recency of use, that combination — hash map for lookup, doubly linked list for reorderable recency — is the standard, close-to-only, answer.
A dictionary for O(1) value lookup, backed by a plain array to track usage order — but updating that order on every access means scanning and shifting the array, which is O(n).
class LRUCacheBruteForce {
private var capacity: Int
private var cache: [Int: Int] = [:]
private var order: [Int] = [] // most-recently-used key sits at the end
init(_ capacity: Int) {
self.capacity = capacity
}
func get(_ key: Int) -> Int {
guard let value = cache[key] else { return -1 }
touch(key)
return value
}
func put(_ key: Int, _ value: Int) {
if cache[key] != nil {
cache[key] = value
touch(key)
return
}
if cache.count == capacity {
let lruKey = order.removeFirst() // O(n) shift of every remaining element
cache.removeValue(forKey: lruKey)
}
cache[key] = value
order.append(key)
}
// Moves `key` to the most-recently-used end — O(n) because it must
// linearly scan the array to find the key's current position.
private func touch(_ key: Int) {
if let index = order.firstIndex(of: key) {
order.remove(at: index) // O(n) shift
}
order.append(key)
}
}
// smoke test — mirrors the canonical LeetCode walkthrough
let bfCache = LRUCacheBruteForce(2)
bfCache.put(1, 1)
bfCache.put(2, 2)
print(bfCache.get(1)) // 1
bfCache.put(3, 3) // evicts key 2 (least recently used)
print(bfCache.get(2)) // -1
bfCache.put(4, 4) // evicts key 1
print(bfCache.get(1)) // -1
print(bfCache.get(3)) // 3
print(bfCache.get(4)) // 4Big-O: get/put are O(n) in the worst case — firstIndex(of:), remove(at:), and removeFirst() all require scanning or shifting the order array. O(n) total space for capacity entries.
A hash map from key to node (for O(1) lookup) paired with a doubly linked list threaded through two dummy sentinels (for O(1) reordering) — the most-recently-used node always sits right after head, the least-recently-used right before tail.
class LRUCache {
private class Node {
let key: Int
var value: Int
var prev: Node?
var next: Node?
init(_ key: Int, _ value: Int) {
self.key = key
self.value = value
}
}
private let capacity: Int
private var map: [Int: Node] = [:]
private let head = Node(-1, -1) // dummy; head.next = most recently used
private let tail = Node(-1, -1) // dummy; tail.prev = least recently used
init(_ capacity: Int) {
self.capacity = capacity
head.next = tail
tail.prev = head
}
func get(_ key: Int) -> Int {
guard let node = map[key] else { return -1 }
remove(node)
insertAtFront(node)
return node.value
}
func put(_ key: Int, _ value: Int) {
if let node = map[key] {
node.value = value
remove(node)
insertAtFront(node)
return
}
if map.count == capacity {
if let lru = tail.prev, lru !== head {
remove(lru)
map.removeValue(forKey: lru.key)
}
}
let node = Node(key, value)
map[key] = node
insertAtFront(node)
}
// Unlink a node from wherever it currently sits — O(1), no scanning.
private func remove(_ node: Node) {
node.prev?.next = node.next
node.next?.prev = node.prev
}
// Insert a node right after the dummy head — the most-recently-used slot.
private func insertAtFront(_ node: Node) {
node.next = head.next
node.prev = head
head.next?.prev = node
head.next = node
}
}
// smoke test — same walkthrough as the brute force
let cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) // 1
cache.put(3, 3) // evicts key 2
print(cache.get(2)) // -1
cache.put(4, 4) // evicts key 1
print(cache.get(1)) // -1
print(cache.get(3)) // 3
print(cache.get(4)) // 4Big-O: get/put are O(1) — dictionary lookup plus a fixed number of pointer relinks, regardless of capacity. O(capacity) total space for the map and the nodes.
The brute force's bottleneck is that an array has no way to move an element to a new position without shifting every element in between — recency tracking is fundamentally a "cut this out from wherever it is, splice it in at the front" operation, and that's precisely what a doubly linked list does in O(1) if you already have a reference to the node. The hash map is what supplies that reference: instead of searching the order structure for a key (the array's O(n) weakness), the map jumps straight to the node in O(1), and the node's own prev/next pointers let it unlink and re-insert itself at the front without touching any other node. Two structures, each covering the other's blind spot — the map gives fast lookup, the list gives fast reordering — is what makes both get and put genuinely O(1).
-
Linked Lists — the doubly linked list is what gives
O(1)eviction and reordering once a node is located; this is the chapter's own headline use case for a doubly linked list. -
Hash Maps & Hash Sets — the
O(1)key-to-node lookup that makes locating a node instant instead of a scan. -
Two Pointers — a stretch here, called out explicitly: LRU Cache is fundamentally a data-structure-design problem, not a named algorithmic pattern; the closest fit is the coordinated
prev/nextpointer updates performed on every insert and evict, the same pointer-relinking skill Two Pointers builds.
LRU Cache is a stack of books re-shelved at the front every time you read one — a hash map finds the book instantly, a doubly linked list re-shelves it instantly, and whatever's drifted to the back gets tossed first.
In the optimal solution, put calls insertAtFront both when a key is brand-new and when an existing key is updated. Explain why an existing key must also be moved to the front on put (not just on get) — what part of the LRU contract would break if put-ing an already-present key left its position in the list unchanged?
⬅️ Previous: Find the Duplicate Number · Next: Merge k Sorted Lists ➡️