LFU Cache Implementation: O(1) Design That Clears LeetCode

Design a cache that evicts the least-frequently-used key in O(1) time. That's LeetCode 460, rated Hard, and it's the data-structure design question that separates engineers who've built eviction machinery from those who've only read about it. LRU was the warm-up. LFU adds frequency counting, tie-breaking by recency, and a minimum tracker — all without breaking O(1).

The trap is shipping an O(n) eviction scan and calling it done. get is trivially O(1) with a hashmap, so candidates feel finished, then TLE on the 10^5-operation stress test because every full-cache insert scans for the minimum. This walkthrough builds that naive version so you can name it, then replaces it with frequency buckets where LRU-within-tie falls out for free.

You'll get runnable Python, the four bugs that flip working-looking code to failing, and the follow-ups interviewers use once the basics pass.

Problem Walkthrough — What O(1) LFU Demands

LeetCode 460: capacity n, operations get(key) → value or -1, put(key, value) inserting or updating. On full-cache insert, evict the least-frequently-used key; ties go to the least-recently-used. All operations must be O(1) average. Up to 10^5 operations, capacity up to 10^4.

Frequency counts accesses (both get and put-on-existing-key bump it). New keys start at freq 1. The canonical sample: capacity 2, put(1,1), put(2,2), get(1)→1, put(3,3) evicts key 2 (freq 1, stale) keeping key 1 (freq 2), get(2)→-1, get(3)→3, get(1)→1.

Note the LeetCode class name is LFUCache with __init__(capacity), not Solution — the test harness instantiates LFUCache directly. Writing class Solution here fails every test regardless of logic.

Brute Force — The Min-Scan That TLEs

The naive design: key→(value, freq) hashmap, get bumps freq in O(1), put-on-existing bumps in O(1) — and eviction scans all keys for min freq, O(n). With capacity 10^4 and 10^5 ops, worst case is ~10^9 comparisons. TLE, guaranteed.

The heap upgrade (entries keyed by (freq, timestamp)) fixes eviction to O(log n) but still misses the O(1) bar, and stale entries after frequency bumps need lazy deletion bookkeeping that doubles the code.

Both versions teach the same lesson: the minimum must be TRACKED (a variable updated on every transition), never SEARCHED. That single realization is the design.

Optimal Approach — Frequency Buckets Plus min_freq

Keep key_to_val (key → value), key_to_freq (key → freq), freq_to_keys (freq → OrderedDict of keys in recency order), and min_freq (smallest freq present). _touch(key): remove from old bucket, bump min_freq if the old bucket emptied at the minimum, append to bucket freq+1.

get: miss → -1; hit → _touch + return value. put: capacity 0 → return; existing key → update value + _touch; full cache → popitem(last=False) from bucket min_freq (LRU-within-tie falls out of OrderedDict order), delete its maps, then insert new key at freq 1 with min_freq = 1.

Why O(1)? Every operation touches a constant number of hashmap/OrderedDict ops. Buckets append and popleft in O(1); min_freq updates are O(1) comparisons. No scans, no heaps, no timestamps.

The Frequency-Bucket Cache in Full Python

All frequency mutation flows through _touch — get and update-put both call it, so counts can't drift. Eviction reads only bucket min_freq, positioned by popitem(last=False) at the stalest key. The capacity-0 guard sits at the top of put before any structure is touched.

The __main__ block runs the canonical sample plus the capacity-0 opener. For deeper safety, fuzz locally: run 10^4 random ops against a naive min-scan reference and assert identical get results — that differential test catches drift bugs no sample covers.

from collections import defaultdict, OrderedDict


class LFUCache:
    """O(1) LFU with freq buckets + min_freq. LeetCode 460 harness name."""

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val: dict[int, int] = {}
        self.key_to_freq: dict[int, int] = {}
        self.freq_to_keys: dict[int, OrderedDict] = defaultdict(OrderedDict)

    def _touch(self, key: int) -> None:
        freq = self.key_to_freq[key]
        val = self.key_to_val[key]
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq] and freq == self.min_freq:
            self.min_freq += 1
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = val

    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._touch(key)
        return self.key_to_val[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._touch(key)
            return
        if len(self.key_to_val) >= self.capacity:
            evict, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[evict]
            del self.key_to_freq[evict]
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = value
        self.min_freq = 1


if __name__ == "__main__":
    c = LFUCache(2)
    c.put(1, 1)
    c.put(2, 2)
    assert c.get(1) == 1
    c.put(3, 3)  # evicts key 2
    assert c.get(2) == -1
    assert c.get(3) == 3
    assert c.get(1) == 1
    z = LFUCache(0)
    z.put(0, 0)
    assert z.get(0) == -1
    print("all checks passed")

Capacity Zero, Ties on Frequency and Repeated Gets

Capacity 0: all puts ignored, all gets -1. Single-slot cache: every new-key put evicts the occupant regardless of its freq — verify put/get alternation. Tie at min freq: keys A then B both freq 1, insert C → A (stalest) evicted; assert B survives.

Update-put bumps freq: put(1,1), put(1,10), then fill — key 1 must survive as freq-2 while a freq-1 key dies. Repeated gets promote: get(x) three times then insert — x must survive over untouched keys.

Stress: 10^5 mixed ops at capacity 10^3 must complete in seconds. If runtime climbs past ~10s locally, an eviction scan or min recompute is hiding somewhere.

Complexity — Why Buckets Are the Only O(1) Answer

Optimal: O(1) average get and put — constant hashmap/OrderedDict operations, no loops over cache contents. O(n) space for the three maps plus buckets (each key stored twice: once in maps, once in a bucket — still linear).

Naive min-scan: O(1) get, O(n) put-on-full — TLE at 10^5 ops. Heap: O(log n) both ops — correct but over budget and burdened with stale-entry cleanup. Reused LRU: O(1) but wrong eviction semantics entirely.

Present the table, then land the line: frequency buckets are the only design where eviction needs no search, because min_freq IS the answer and bucket order IS the tie-break.