LFU Cache (LeetCode 460)
A cache with a fixed capacity should evict its least frequently used key once full, breaking ties between equally-frequent keys by evicting whichever one was touched longest ago.
Build an LFUCache class:
LFUCache(int capacity)sets up the cache with the givencapacity.int get(int key)returns the value stored forkey, or-1ifkeyisn't present.void put(int key, int value)overwriteskey's value if it's already present, or inserts it otherwise; once the cache is atcapacity, this first evicts the least frequently used key (the tie-break above applies).
Every key carries a use counter: a fresh put sets it to 1, and both get and put on an existing key bump its counter by one. The least frequently used key is simply the one with the smallest counter.
Both get and put must run in O(1) average time.
Worked Examples
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]][null, null, null, 1, null, -1, 3, null, -1, 3, 4]⚖️Formal Constraints & Bounds
1 <= capacity <= 1040 <= key <= 1050 <= value <= 109At most 2 * 105 calls will be made to get and put.
Core Insight
Frequencies only ever change by exactly +1 per access, so one small doubly-linked-list bucket per frequency (plus a running min_freq pointer that only advances when its bucket empties) delivers O(1) promotion and O(1) eviction, with ties among equal frequencies broken by LRU order within the bucket.
Real-World Scenario & Production Applications
CPU cache replacement policies weighting access frequency over recency, database buffer pool eviction, CDN caching for content whose popularity (not just recency) determines retention value.
Subproblems & Recurrence Decomposition3 Phases
One hash map (key_node) resolves any key to its node in O(1). A second hash map (freq_bucket) resolves any frequency value to the doubly-linked-list bucket of every key currently at that exact frequency.
self.key_node = {} # key -> Node(value, freq)
self.freq_bucket = {} # freq -> DLList of keys at that freqStep-by-Step Execution Trace Table
| Step | Operation | min_freq | Frequency Buckets (freq -> [Keys]) | Evicted Key | Output |
|---|---|---|---|---|---|
| 1 | LFUCache(2) | 0 | {} | - | null |
| 2 | put(1, 1) | 1 | {1: [1]} | - | null |
| 3 | put(2, 2) | 1 | {1: [2, 1]} (MRU -> LRU) | - | null |
| 4 | get(1) | 1 | {1: [2], 2: [1]} | - | 1 (key 1 freq promoted to 2) |
| 5 | put(3, 3) | 1 | Capacity full! Evict LRU from min_freq=1 (key 2). {1: [3], 2: [1]} | 2 | null |
| 6 | get(2) | 1 | {1: [3], 2: [1]} | - | -1 (key 2 was evicted) |
| 7 | get(3) | 2 | Key 3 promoted: freq 2. Bucket 1 now empty, min_freq = 2. {2: [3, 1]} | - | 3 |
| 1 | self.key_node = {} # key -> Node |
| 2 | self.freq_bucket = {} # freq -> DLList (LRU-ordered within freq) |
| 3 | self.min_freq tracks the lowest occupied bucket |
| 4 | get/put on existing key -> _bump_freq: pop bucket[f], push front bucket[f+1] |
| 5 | put on new key at capacity -> evict tail of bucket[min_freq] |
Conceptual Narrative
LRU Cache only asks "when was this key touched last?" LFU Cache asks a harder two-dimensional question: "how often has this key been touched, and among the least frequent, which is stalest?"—in strict O(1) time.
🧭 Conceptual Foundation & Pattern Intuition
Least Frequently Used (LFU) evicts the key with the lowest access frequency. If multiple keys tie for minimum frequency, it evicts the least recently used among them.
A min-heap tracking frequency costs on every get and put, which violates the strict requirement of LC 460.
How do we achieve strict without sorting? The key insight is that access frequencies only ever change by per operation:
- A key's frequency starts at 1 and increments by exactly 1 on each access. It never jumps arbitrarily.
- Instead of a single sorted structure, we maintain a ladder of frequency buckets (
freq_to_dll), where each bucket is its own independent Doubly-Linked List containing all nodes that share that exact frequency. - Inside each frequency bucket, nodes are ordered by recency (LRU order).
- We maintain a global scalar
min_freq. When an item's frequency increases from to , it is unlinked from bucket and prepended to bucket . If bucket becomes empty andF == min_freq, we incrementmin_freq += 1. - When eviction is required, we simply pop the tail node from bucket
min_freq.
🗄️ The Analogy: The Tiered Airport Lounge Priority Shelves
Imagine an airport lounge with luggage shelves numbered by tier: Shelf 1 (visited once), Shelf 2 (visited twice), Shelf 3, etc. Within any shelf, bags are lined up left-to-right by arrival time. When a passenger visits their bag on Shelf 2, the attendant unlinks it from Shelf 2 and places it at the front of Shelf 3. If Shelf 2 was the lowest occupied shelf and just became completely empty, the attendant moves the "lowest tier" sticky note from Shelf 2 to Shelf 3. When the lounge exceeds capacity, the attendant walks directly to the lowest occupied shelf and removes the bag at the very back—guaranteeing least-frequent eviction with an LRU tiebreaker in constant time.
🔑 Why It Works
Tracking min_freq requires zero search: fresh keys reset it to 1, while existing key updates only ever increment it when its former bucket empties out.
Failing to update
min_freqon node promotion: When a node with frequency equal tomin_freqis accessed and its count becomesmin_freq + 1, if its frequency list becomes empty,min_freqmust increment by 1.Tie-breaking eviction violation: When multiple keys share the lowest frequency, the problem requires evicting the least recently used among them. Each frequency bucket must be a doubly-linked list ordered by access recency.
Updating frequency in search instead of node relocation: Using a heap or linear scan to track minimum frequencies results in operations. A map from frequency to doubly-linked list (
freq_map[f] = DoublyLinkedList()) guarantees strict get and put.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Key-value cache bounded by capacity + O(1) get/put + eviction by LEAST FREQUENTLY used, tie-broken by least recently used.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a key's frequency only ever increases by exactly 1 per access, so it moves from bucket f to bucket f+1 in O(1); min_freq only needs to advance when bucket[min_freq] becomes empty, never requiring a scan.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to reset min_freq to 1 on every brand-new key insertion (a fresh key is, by definition, the new minimum frequency).
Not deleting an emptied frequency bucket from the freq_bucket map, causing stale empty buckets to be mistaken for the min_freq target later.
Breaking the LRU tiebreak within a frequency bucket: inserting at the wrong end (must insert_front so eviction always pops the tail = least recently used at that frequency).
Using a single global frequency counter instead of per-key freq, which loses the ability to bucket by exact frequency.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I pair a hash map (key -> Node holding value and freq) with a second hash map (freq -> doubly-linked-list bucket of keys at that exact frequency, LRU-ordered). A running min_freq pointer always identifies the lowest occupied bucket. On get or put-on-existing-key, I remove the node from its current bucket, bump freq by 1, and reinsert at the front of the new bucket -- advancing min_freq only if the old bucket just emptied. On put of a brand-new key at capacity, I evict the tail of bucket[min_freq] (the least-recently-used key among the least-frequently-used), insert the new key at frequency 1, and reset min_freq to 1. Every operation is
O(1)pointer surgery."
Complexity & Mathematical Proof
O(1) Average
Look at both get(key) and put(key, value): key_node gives O(1) average lookup of the node holding value and freq. freq_bucket gives O(1) average lookup of the doubly-linked-list bucket for any frequency. Removing a node from its bucket and reinserting at the front of the next bucket (_bump_freq) touches a fixed number of pointer fields, O(1). min_freq is only ever read or incremented by 1, never recomputed by scanning. Eviction pops the tail of bucket[min_freq], also O(1). Every operation is strictly O(1) average time.
O(C) Auxiliary
Look at memory allocation: the cache holds at most capacity entries, so key_node holds O(C) entries. freq_bucket holds at most O(C) buckets (one per distinct frequency currently present, bounded by C), each bucket's total node count summing to O(C) across all buckets. Total auxiliary space is O(C).
Derivation Progression
key_node locates the node; freq_bucket locates its frequency's doubly-linked-list bucket, both O(1) average.
Removing from bucket[f] and inserting at the front of bucket[f+1] (creating it if absent) is fixed-cost pointer surgery.
min_freq is incremented by exactly 1 only when its own bucket becomes empty, and reset to 1 on a fresh insert -- never recomputed by scanning all buckets.
Variable Definitions
Maximum cache capacity
Total number of get and put operations performed
Memory Architecture & Bounds
O(1) Non-recursive method calls
O(C) key_node map of size C + freq_bucket map whose bucket node counts sum to C
O(1) Scalar return values
Boundary Best / Worst Cases
for both get and put operations.
standard hash table distribution.
amortized average ( in rare catastrophic hash collision degeneration).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "LFU Cache", "tie-breaker is least recently used", "O(1) time complexity". Two-level indexing: keys are grouped by frequency, and within the same frequency, ordered by recency. A Senior SWE uses key_to_node map + freq_to_dll map + min_freq integer.
Capacity , up to calls. Strictly per get and put.
Capacity 0 base case (no-op on put, return -1 on get).
LFU Cache (LeetCode 460)
A cache with a fixed capacity should evict its least frequently used key once full, breaking ties between equally-frequent keys by evicting whichever one was touched longest ago.
Build an LFUCache class:
LFUCache(int capacity)sets up the cache with the givencapacity.int get(int key)returns the value stored forkey, or-1ifkeyisn't present.void put(int key, int value)overwriteskey's value if it's already present, or inserts it otherwise; once the cache is atcapacity, this first evicts the least frequently used key (the tie-break above applies).
Every key carries a use counter: a fresh put sets it to 1, and both get and put on an existing key bump its counter by one. The least frequently used key is simply the one with the smallest counter.
Both get and put must run in O(1) average time.
Worked Examples
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]][null, null, null, 1, null, -1, 3, null, -1, 3, 4]⚖️Formal Constraints & Bounds
1 <= capacity <= 1040 <= key <= 1050 <= value <= 109At most 2 * 105 calls will be made to get and put.
Core Insight
Frequencies only ever change by exactly +1 per access, so one small doubly-linked-list bucket per frequency (plus a running min_freq pointer that only advances when its bucket empties) delivers O(1) promotion and O(1) eviction, with ties among equal frequencies broken by LRU order within the bucket.
Real-World Scenario & Production Applications
CPU cache replacement policies weighting access frequency over recency, database buffer pool eviction, CDN caching for content whose popularity (not just recency) determines retention value.
Subproblems & Recurrence Decomposition3 Phases
One hash map (key_node) resolves any key to its node in O(1). A second hash map (freq_bucket) resolves any frequency value to the doubly-linked-list bucket of every key currently at that exact frequency.
self.key_node = {} # key -> Node(value, freq)
self.freq_bucket = {} # freq -> DLList of keys at that freqStep-by-Step Execution Trace Table
| Step | Operation | min_freq | Frequency Buckets (freq -> [Keys]) | Evicted Key | Output |
|---|---|---|---|---|---|
| 1 | LFUCache(2) | 0 | {} | - | null |
| 2 | put(1, 1) | 1 | {1: [1]} | - | null |
| 3 | put(2, 2) | 1 | {1: [2, 1]} (MRU -> LRU) | - | null |
| 4 | get(1) | 1 | {1: [2], 2: [1]} | - | 1 (key 1 freq promoted to 2) |
| 5 | put(3, 3) | 1 | Capacity full! Evict LRU from min_freq=1 (key 2). {1: [3], 2: [1]} | 2 | null |
| 6 | get(2) | 1 | {1: [3], 2: [1]} | - | -1 (key 2 was evicted) |
| 7 | get(3) | 2 | Key 3 promoted: freq 2. Bucket 1 now empty, min_freq = 2. {2: [3, 1]} | - | 3 |
| 1 | self.key_node = {} # key -> Node |
| 2 | self.freq_bucket = {} # freq -> DLList (LRU-ordered within freq) |
| 3 | self.min_freq tracks the lowest occupied bucket |
| 4 | get/put on existing key -> _bump_freq: pop bucket[f], push front bucket[f+1] |
| 5 | put on new key at capacity -> evict tail of bucket[min_freq] |
Conceptual Narrative
LRU Cache only asks "when was this key touched last?" LFU Cache asks a harder two-dimensional question: "how often has this key been touched, and among the least frequent, which is stalest?"—in strict O(1) time.
🧭 Conceptual Foundation & Pattern Intuition
Least Frequently Used (LFU) evicts the key with the lowest access frequency. If multiple keys tie for minimum frequency, it evicts the least recently used among them.
A min-heap tracking frequency costs on every get and put, which violates the strict requirement of LC 460.
How do we achieve strict without sorting? The key insight is that access frequencies only ever change by per operation:
- A key's frequency starts at 1 and increments by exactly 1 on each access. It never jumps arbitrarily.
- Instead of a single sorted structure, we maintain a ladder of frequency buckets (
freq_to_dll), where each bucket is its own independent Doubly-Linked List containing all nodes that share that exact frequency. - Inside each frequency bucket, nodes are ordered by recency (LRU order).
- We maintain a global scalar
min_freq. When an item's frequency increases from to , it is unlinked from bucket and prepended to bucket . If bucket becomes empty andF == min_freq, we incrementmin_freq += 1. - When eviction is required, we simply pop the tail node from bucket
min_freq.
🗄️ The Analogy: The Tiered Airport Lounge Priority Shelves
Imagine an airport lounge with luggage shelves numbered by tier: Shelf 1 (visited once), Shelf 2 (visited twice), Shelf 3, etc. Within any shelf, bags are lined up left-to-right by arrival time. When a passenger visits their bag on Shelf 2, the attendant unlinks it from Shelf 2 and places it at the front of Shelf 3. If Shelf 2 was the lowest occupied shelf and just became completely empty, the attendant moves the "lowest tier" sticky note from Shelf 2 to Shelf 3. When the lounge exceeds capacity, the attendant walks directly to the lowest occupied shelf and removes the bag at the very back—guaranteeing least-frequent eviction with an LRU tiebreaker in constant time.
🔑 Why It Works
Tracking min_freq requires zero search: fresh keys reset it to 1, while existing key updates only ever increment it when its former bucket empties out.
Failing to update
min_freqon node promotion: When a node with frequency equal tomin_freqis accessed and its count becomesmin_freq + 1, if its frequency list becomes empty,min_freqmust increment by 1.Tie-breaking eviction violation: When multiple keys share the lowest frequency, the problem requires evicting the least recently used among them. Each frequency bucket must be a doubly-linked list ordered by access recency.
Updating frequency in search instead of node relocation: Using a heap or linear scan to track minimum frequencies results in operations. A map from frequency to doubly-linked list (
freq_map[f] = DoublyLinkedList()) guarantees strict get and put.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Key-value cache bounded by capacity + O(1) get/put + eviction by LEAST FREQUENTLY used, tie-broken by least recently used.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a key's frequency only ever increases by exactly 1 per access, so it moves from bucket f to bucket f+1 in O(1); min_freq only needs to advance when bucket[min_freq] becomes empty, never requiring a scan.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to reset min_freq to 1 on every brand-new key insertion (a fresh key is, by definition, the new minimum frequency).
Not deleting an emptied frequency bucket from the freq_bucket map, causing stale empty buckets to be mistaken for the min_freq target later.
Breaking the LRU tiebreak within a frequency bucket: inserting at the wrong end (must insert_front so eviction always pops the tail = least recently used at that frequency).
Using a single global frequency counter instead of per-key freq, which loses the ability to bucket by exact frequency.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I pair a hash map (key -> Node holding value and freq) with a second hash map (freq -> doubly-linked-list bucket of keys at that exact frequency, LRU-ordered). A running min_freq pointer always identifies the lowest occupied bucket. On get or put-on-existing-key, I remove the node from its current bucket, bump freq by 1, and reinsert at the front of the new bucket -- advancing min_freq only if the old bucket just emptied. On put of a brand-new key at capacity, I evict the tail of bucket[min_freq] (the least-recently-used key among the least-frequently-used), insert the new key at frequency 1, and reset min_freq to 1. Every operation is
O(1)pointer surgery."
Complexity & Mathematical Proof
O(1) Average
Look at both get(key) and put(key, value): key_node gives O(1) average lookup of the node holding value and freq. freq_bucket gives O(1) average lookup of the doubly-linked-list bucket for any frequency. Removing a node from its bucket and reinserting at the front of the next bucket (_bump_freq) touches a fixed number of pointer fields, O(1). min_freq is only ever read or incremented by 1, never recomputed by scanning. Eviction pops the tail of bucket[min_freq], also O(1). Every operation is strictly O(1) average time.
O(C) Auxiliary
Look at memory allocation: the cache holds at most capacity entries, so key_node holds O(C) entries. freq_bucket holds at most O(C) buckets (one per distinct frequency currently present, bounded by C), each bucket's total node count summing to O(C) across all buckets. Total auxiliary space is O(C).
Derivation Progression
key_node locates the node; freq_bucket locates its frequency's doubly-linked-list bucket, both O(1) average.
Removing from bucket[f] and inserting at the front of bucket[f+1] (creating it if absent) is fixed-cost pointer surgery.
min_freq is incremented by exactly 1 only when its own bucket becomes empty, and reset to 1 on a fresh insert -- never recomputed by scanning all buckets.
Variable Definitions
Maximum cache capacity
Total number of get and put operations performed
Memory Architecture & Bounds
O(1) Non-recursive method calls
O(C) key_node map of size C + freq_bucket map whose bucket node counts sum to C
O(1) Scalar return values
Boundary Best / Worst Cases
for both get and put operations.
standard hash table distribution.
amortized average ( in rare catastrophic hash collision degeneration).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "LFU Cache", "tie-breaker is least recently used", "O(1) time complexity". Two-level indexing: keys are grouped by frequency, and within the same frequency, ordered by recency. A Senior SWE uses key_to_node map + freq_to_dll map + min_freq integer.
Capacity , up to calls. Strictly per get and put.
Capacity 0 base case (no-op on put, return -1 on get).