LFU Cache
LFU Cache: O(1) cache evicting the least frequently used key; ties broken by least recent.
- 1 <= capacity <= 10⁴
- 0 <= key <= 10⁵
- 0 <= value <= 10⁹
- At most 2 * 10⁵ calls will be made to get and put.
Intuition
An lfu cache evicts the least frequently used key, breaking ties by least recently used. Both parts of that rule have to be answered in O(1), which is what makes it harder than LRU.
A single ordering cannot express it. Sorting by frequency loses recency; sorting by recency loses frequency. So bucket the keys instead: group every key by its exact use count, and within each bucket keep insertion order so the oldest is identifiable.
That gives the structure directly — a map from frequency to an ordered collection of keys. Eviction needs the least frequent bucket, and scanning to find it would be O(n), so track it explicitly:
- Keep minFreq, the lowest frequency currently in use.
The reason a single integer suffices is subtle and worth stating. minFreq only ever changes in two ways. Inserting a new key sets it to 1, since a fresh key has been used once. And promoting a key out of the minimum bucket raises it by exactly one — but only if that bucket is now empty. It can never jump by more than one, because a key moves from f to f + 1 and nowhere else.
With that invariant, eviction is: take the oldest key from buckets[minFreq]. Every operation is a hash or ordered-dictionary step, so the whole cache runs in O(1).
LFU needs two orderings at once — by frequency, and by recency within a frequency. A dict of frequency to ordered-dict gives both, and tracking minf makes eviction O(1) instead of a scan for the smallest count. The key realisation: minf only ever increases by one, and only when the bucket it points at empties.
Approach
Before reading on: price up what counting everything costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(1) per op time and O(capacity) space.
Store three pieces of state
A vals map from key to (value, frequency), a buckets map from frequency to an ordered collection of keys, and an integer minFreq. The buckets are what let frequency and recency coexist — frequency picks the bucket, insertion order within it settles the tie.
Use an insertion-ordered container per bucket
Python's OrderedDict or a doubly linked list works. You need O(1) removal from the middle when a key is promoted, and O(1) removal of the oldest when evicting — a plain list gives you one or the other, not both.
Promote a key on every touch
On get or an overwriting put, remove the key from buckets[f] and add it to buckets[f + 1], updating its stored frequency. Adding at the end preserves recency order, so the promoted key is now the most recent within its new bucket.
Raise minFreq only when its bucket empties
After promoting a key out of buckets[minFreq], if that bucket is now empty, increment minFreq. It can rise by exactly one and no more, because a key moves from f to f + 1 — this is why a single integer tracks it correctly.
Evict before inserting when full
When capacity is reached and a genuinely new key arrives, remove the oldest key from buckets[minFreq] first. That is the least frequently used, and the oldest among ties — both halves of the eviction rule satisfied by one operation.
Reset minFreq to 1 on a new key
A newly inserted key has frequency 1, so minFreq becomes 1 unconditionally. Doing this after the eviction matters — evicting first uses the old minimum, which is the correct one to evict from.
Cost of the design
Every operation is a constant number of hash and ordered-container steps, giving O(1) time for both get and put. Space is O(capacity) across the two maps.
Solution & live demo
Common pitfalls
Scanning for the minimum frequency on eviction
f = min(self.buckets) old, _ = self.buckets[f].popitem(last=False)
old, _ = self.buckets[self.minf].popitem(last=False)
That's O(number of distinct frequencies) per eviction, breaking the O(1) requirement. Maintaining minf incrementally is possible because a promotion can only empty the current minimum bucket, in which case the new minimum is exactly one higher.
Not resetting minf to 1 on insert
self.vals[key] = [value, 1] self.buckets[1][key] = None
self.vals[key] = [value, 1] self.buckets[1][key] = None self.minf = 1
A brand-new key has frequency 1, which is the global minimum by definition. Leaving minf higher makes the next eviction look in an empty or wrong bucket and throw, or evict a more valuable entry.
Treating an update as a plain overwrite
if key in self.vals:
self.vals[key][0] = value
returnif key in self.vals:
self.vals[key][0] = value
self._touch(key); returnput on an existing key counts as a use, so its frequency must rise like a get. Skipping the touch leaves the entry looking colder than it is and it gets evicted ahead of genuinely stale keys.
Edge cases
Value update counts as a use — promote, don't evict.
Every put is a no-op; guard first.