LFU Cache

LFU Cache is a classic hard design problem. The twist over LRU is that we evict by how often an entry has been used, not by how recently — and we still have to make every get and put run in O(1).

The slow way first

The naive cache stores entries plus a use-count, and on eviction it scans every entry to find the minimum count. That scan is O(n) per put — too slow. Sorting entries by frequency does not help either: a single get changes one count, and re-sorting is O(n log n).

The question to ask: can I jump straight to the lowest-frequency entry without scanning? If I keep entries grouped by frequency, I can.

The idea: group by frequency, track the minimum

Keep two maps and one number:

• key_to_node — maps a key directly to its node, so any lookup is O(1).
• freq_buckets — maps a frequency to a doubly linked list of every node at that frequency, kept in most-recently-used order. Adding or removing a node from a DLL is O(1).
• min_freq — the smallest non-empty frequency. The eviction victim always lives at the front of the min_freq bucket.

A get or put uses an entry, so it bumps that node from its bucket to the next-higher bucket. Eviction reads straight from the min_freq bucket — no scan.

The key insight: min_freq only ever rises when a get empties the current min bucket, and it resets to 1 on every fresh insert (a new entry always starts at frequency 1).

Walk through it

Step through the animation. A and B start in the freq-1 bucket. get(A) slides A into the freq-2 bucket, but min_freq stays 1 because B is still there. Then put(C) finds the cache full, evicts B from the min_freq bucket, inserts C at frequency 1, and resets min_freq to 1.

Pseudocode

maps: key_to_node, freq_buckets   # freq -> doubly linked list
min_freq = 0
 
get(key):
    if key not in key_to_node: return -1
    bump(key)                      # freq += 1, move node to next bucket
    if min_freq bucket is now empty: min_freq += 1
    return node.value
 
put(key, val):
    if capacity == 0: return
    if size >= capacity:
        victim = front of min_freq bucket   # least-freq, least-recent
        remove victim from key_to_node and its bucket
    add new node at frequency 1
    min_freq = 1                    # a fresh insert is always freq 1

The Python solution

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.key_to_node = {}       # key -> node
        self.freq_buckets = {}      # freq -> DLL of nodes
        self.min_freq = 0
 
    def get(self, key):
        if key not in self.key_to_node:
            return -1
        self._bump(key)             # freq += 1, move bucket
        if not self.freq_buckets[self.min_freq]:
            self.min_freq += 1
        return self.key_to_node[key].val
 
    def put(self, key, val):
        if self.cap == 0:
            return
        if len(self.key_to_node) >= self.cap:
            victim = self.freq_buckets[self.min_freq].pop_lru()
            del self.key_to_node[victim.key]
        node = self._add(key, val)  # new node at freq 1
        self.freq_buckets[1].push(node)
        self.min_freq = 1

• key_to_node is the index that makes any lookup O(1) — no walking lists to find an entry.
• freq_buckets[f] is a doubly linked list of every node at frequency f, ordered most-recent-first, so pushing a bumped node or popping the LRU victim is O(1).
• _bump removes the node from its current bucket and appends it to the freq+1 bucket — that is the slide you see in the animation.
• After a bump, if the old min_freq bucket became empty, min_freq rises by one (line 12-13).
• On put, eviction reads the victim straight from the min_freq bucket (line 20) — no scan.
• Every fresh insert lands at frequency 1, so min_freq resets to 1 (line 24).

Complexity

We spend O(n) space on the two maps and the bucket lists, and in return every get and put is constant time. The trick — group items by a key so the extreme is always at a known spot — is the same move behind bucket sort and the LRU cache.

When this pattern shows up

Practice