LFU Cache
Design a least frequently used cache with O(1) get and put, breaking ties between equally used keys by evicting the least recently used one.
Problem Understanding
LFU Cache (LeetCode 460): design a cache with a fixed capacity. get(key) returns the value or -1. put(key, value) updates or inserts; when the cache is full, it first evicts the least frequently used key, and if several keys tie on that count, the least recently used of them. A key's count goes up on every get and put that touches it. Both operations must run in O(1) on average.
The Intuition: One LRU List per Use Count
LRU Cache keeps one list ordered by recency. LFU needs the same thing, split by how often each key was used.
- Group keys by count. Each count has its own list, least recent first. Within a count, the order breaks ties exactly as LRU would.
- Touch = move up one row. A used key leaves count f and joins the end of count f + 1.
- Track minFreq. It only changes in two ways: a touch that empties the minimum row raises it by one, and a new key resets it to 1. That is why finding the key to evict never needs a search.
Interactive Walkthrough
CAPACITY 2
EMPTY CACHE
no keys yet
EACH ROW: LEAST RECENT ← → MOST RECENT
Operation
:
Size
0/2
minFreq
0
get returns
No gets yet
An empty cache with capacity 2: no keys, no counts, minFreq = 0
Next
put(1, 1): a new key starts at count 1, so minFreq = 1
Operations
capacity
Each row is one use count, least recent key on the left; the minFreq row is marked. Try Frequent survives: key 1 was added first, but it was read three times, so the newer key 2 is the one evicted.
Dry Run Table
Input: capacity 2, then put(1,1), put(2,2), get(1), put(3,3), get(2), get(3), put(4,4), get(1), get(3), get(4). Rows are count: keys, least recent first.
| Operation | What happens | Rows after | minFreq | Returns |
|---|---|---|---|---|
| put(1, 1) | new key at count 1 | 1: [1] | 1 | |
| put(2, 2) | new key at count 1 | 1: [1, 2] | 1 | |
| get(1) | 1 moves to count 2 | 1: [2], 2: [1] | 1 | 1 |
| put(3, 3) | full: evict 2, the only key at count 1 | 1: [3], 2: [1] | 1 | |
| get(2) | not cached | 1: [3], 2: [1] | 1 | -1 |
| get(3) | 3 moves to count 2; count 1 is empty, so minFreq rises | 2: [1, 3] | 2 | 3 |
| put(4, 4) | full: evict 1, the oldest key at count 2 | 1: [4], 2: [3] | 1 | |
| get(1) | not cached | 1: [4], 2: [3] | 1 | -1 |
| get(3) | 3 moves to count 3 | 1: [4], 3: [3] | 1 | 3 |
| get(4) | 4 moves to count 2; count 1 is empty | 2: [4], 3: [3] | 2 | 4 |
Returns: 1, -1, 3, -1, 3, 4.
The Solution Template
A key map, a map from count to an ordered set of keys, and minFreq. Python uses OrderedDict, Java LinkedHashSet, JavaScript and TypeScript a Set (which keeps insertion order), C++ a list with saved iterators, and C fixed arrays as doubly linked lists, since LeetCode keys are 0 to 10^5.
LFU Cache Code
1class LFUCache {2 constructor(capacity) {3 this.capacity = capacity;4 this.entries = new Map(); // key -> { value, freq }5 this.freqs = new Map(); // count -> Set of keys, least recent first6 this.minFreq = 0;7 }89 touch(key) {10 const entry = this.entries.get(key);11 const f = entry.freq;12 this.freqs.get(f).delete(key);13 if (this.freqs.get(f).size === 0 && this.minFreq === f) {14 this.minFreq++;15 }16 entry.freq = f + 1;17 if (!this.freqs.has(f + 1)) this.freqs.set(f + 1, new Set());18 this.freqs.get(f + 1).add(key);19 }2021 get(key) {22 if (!this.entries.has(key)) {23 return -1;24 }25 this.touch(key);26 return this.entries.get(key).value;27 }2829 put(key, value) {30 if (this.capacity === 0) {31 return;32 }33 if (this.entries.has(key)) {34 this.entries.get(key).value = value;35 this.touch(key);36 return;37 }38 if (this.entries.size === this.capacity) {39 const old = this.freqs.get(this.minFreq).values().next().value;40 this.freqs.get(this.minFreq).delete(old);41 this.entries.delete(old);42 }43 this.entries.set(key, { value, freq: 1 });44 if (!this.freqs.has(1)) this.freqs.set(1, new Set());45 this.freqs.get(1).add(key);46 this.minFreq = 1;47 }48}
Edge Cases & Common Mistakes
- Capacity 0: put does nothing and every get returns -1.
- Updating an existing key: change the value and touch it; do not evict anything, and do not reset its count to 1.
- Ties: among keys with the lowest count, evict the least recently used, which is the first one in that count's list.
- Forgetting minFreq: if a touch empties the minimum row, minFreq must move up, or the next eviction looks in an empty list.
- Evicting after inserting: evict first, then insert. Inserting first puts the new key at count 1, where it would be evicted at once.
Summary
Map each key to its value and use count, keep one least-recent-first list per count, and track minFreq. A use moves the key up one count; a new key evicts the first key at minFreq when full, then starts at count 1. O(1) get and put, O(capacity) space.
More practice: DSA interview questions with answers · patterns cheat sheet