LeetCode #460 Hard

LFU Cache

O(1) cache evicting the least frequently used key; ties broken by least recent.

designhash-tablelfu

02

Intuition

Group keys by use-count: freq → an ordered set of keys (insertion order = recency). Track the minimum frequency. A touch moves a key from bucket f to f+1; eviction pops the oldest key from the min-freq bucket. Every step is a dict/OrderedDict operation — O(1).

How to spot this pattern

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.

03

Approach

1

Two maps + a counter

vals key→(value,freq); buckets freq→OrderedDict of keys; minf = current lowest frequency.

2

Touch promotes

Remove key from bucket f; add to bucket f+1. If bucket f was the min and is now empty, minf += 1 (the only way minf rises).

3

Insert resets minf

A new key has freq 1 → minf = 1. Eviction (before insert, when full): popitem(last=False) on bucket minf = oldest of the least-used.

04

Solution & live demo

▶1from collections import defaultdict, OrderedDict
▶2 
▶3class LFUCache:
▶4    def __init__(self, capacity):
▶5        self.cap = capacity
▶6        self.vals = {}                        # key -> [value, freq]
▶7        self.buckets = defaultdict(OrderedDict)  # freq -> keys (ordered)
▶8        self.minf = 0
▶9 
▶10    def _touch(self, key):
▶11        value, f = self.vals[key]
▶12        del self.buckets[f][key]
▶13        if self.minf == f and not self.buckets[f]:
▶14            self.minf = f + 1
▶15        self.buckets[f + 1][key] = None
▶16        self.vals[key][1] = f + 1
▶17 
▶18    def get(self, key):
▶19        if key not in self.vals: return -1
▶20        self._touch(key)
▶21        return self.vals[key][0]
▶22 
▶23    def put(self, key, value):
▶24        if self.cap == 0: return
▶25        if key in self.vals:
▶26            self.vals[key][0] = value
▶27            self._touch(key); return
▶28        if len(self.vals) == self.cap:
▶29            old, _ = self.buckets[self.minf].popitem(last=False)
▶30            del self.vals[old]
▶31        self.vals[key] = [value, 1]
▶32        self.buckets[1][key] = None
▶33        self.minf = 1

05

Common pitfalls

Scanning for the minimum frequency on eviction

✗ Wrong

f = min(self.buckets)
old, _ = self.buckets[f].popitem(last=False)

✓ Right

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

✗ Wrong

self.vals[key] = [value, 1]
self.buckets[1][key] = None

✓ Right

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

✗ Wrong

if key in self.vals:
    self.vals[key][0] = value
    return

✓ Right

if key in self.vals:
    self.vals[key][0] = value
    self._touch(key); return

put 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.

06

Edge cases

put on existing key

Value update counts as a use — promote, don't evict.

capacity 0

Every put is a no-op; guard first.

07

Complexity

Time

O(1) per op

Space

O(capacity)

OrderedDict gives O(1) oldest-key eviction.