LFU Cache (LeetCode 460)

The problem

Design a cache with a fixed capacity that supports, in O(1) average time:

• get(key): return the value, or −1 if absent. A successful get counts as one use;
• put(key, value): insert or update the key (an update also counts as a use). If inserting a new key into a full cache, first evict the least frequently used key. If several keys tie on frequency, evict the least recently used of them.

capacity = 2
put(1, 1), put(2, 2)
get(1)    -> 1        key 1 used twice, key 2 once
put(3, 3)             full: evict key 2 (lowest count)
get(2)    -> -1
get(3)    -> 3        keys 1 and 3 both used twice now
put(4, 4)             tie on count 2: evict key 1 (used less recently)
get(1)    -> -1
get(3)    -> 3
get(4)    -> 4

How to think about it

Start with brute force. Store key → (value, count, last_used_time). On eviction, scan every key for the smallest (count, last_used_time). Each get is O(1), but eviction is O(capacity). A heap ordered by (count, time) improves eviction to O(log n), but every get changes a key’s count, and updating an item deep inside a heap is awkward and still O(log n).

The key insight: group keys by frequency. Keep a map freq → bucket of keys with that count. When a key is used, move it from bucket f to bucket f + 1: two O(1) operations. Make each bucket an OrderedDict, so keys inside a bucket stay in the order they arrived. The oldest key in a bucket is then the least recently used among those with that count, which handles the tie-break for free.

The last piece: know which bucket to evict from. Keep minf, the smallest frequency currently present. It only changes in two predictable ways. A new key always has count 1, so after an insert minf = 1. When a use empties the bucket that was minf, the key that left it now has minf + 1, so minf goes up by exactly one. Eviction is then “pop the oldest key from buckets[minf]”, in O(1).

Which pattern is this? Design a data structure, the harder sibling of LRU: hash maps for lookup, ordered buckets for eviction order, and a pointer to the eviction bucket. The tell is “evict by frequency, ties by recency, all in O(1)“. Name your structures before writing code.

Approach

1. Keep val (key → value), freq (key → count), buckets (count → OrderedDict of keys), and minf.
2. _touch(key): remove the key from buckets[f]. If that bucket is now empty, delete it and, if f was minf, increase minf. Then set the count to f + 1 and add the key to the end of buckets[f + 1].
3. get(key): return −1 if absent; otherwise _touch it and return its value.
4. put(key, value): if capacity is 0, do nothing. If the key exists, update its value and _touch it. Otherwise, if full, pop the oldest key from buckets[minf] and delete it from val and freq. Then insert the new key with count 1 into buckets[1] and set minf = 1.

Solution

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, cap):
        self.cap = cap; self.val = {}; self.freq = {}
        self.buckets = defaultdict(OrderedDict); self.minf = 0   # freq -> keys in recency order
    def _touch(self, key):
        f = self.freq[key]; del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.minf == f: self.minf += 1                    # min bucket emptied: min moves up by 1
        self.freq[key] = f + 1; self.buckets[f + 1][key] = None  # newest end of the next bucket
    def get(self, key):
        if key not in self.val: return -1
        self._touch(key); return self.val[key]
    def put(self, key, value):
        if self.cap <= 0: return
        if key in self.val:
            self.val[key] = value; self._touch(key); return
        if len(self.val) >= self.cap:
            k, _ = self.buckets[self.minf].popitem(last=False)  # LFU, oldest on ties
            del self.val[k]; del self.freq[k]
        self.val[key] = value; self.freq[key] = 1
        self.buckets[1][key] = None; self.minf = 1               # new key: min frequency is 1
# cap=2: put(1,1) put(2,2) get(1)->1 put(3,3) get(2)->-1 get(3)->3 put(4,4) get(1)->-1 get(3)->3 get(4)->4

Dry run

With capacity 2. Buckets list keys oldest first:

At get(3) the count-1 bucket empties, so minf moves to 2. At put(4,4), bucket 2 holds [1, 3] and key 1 is older, so it is evicted.

Complexity

• Time: O(1) average per operation. Every step is a hash-map or OrderedDict insert, delete or pop from the front, and minf changes by a constant amount.
• Space: O(capacity). Each cached key appears once in val, freq and one bucket.

Edge cases and pitfalls

• Capacity 0: put must store nothing and get always returns −1.
• Updating an existing key counts as a use and must not trigger an eviction.
• Resetting minf to 1 on insert is required; forgetting it leaves minf pointing at a higher bucket and evicts the wrong key.
• Evict before inserting. If you insert first, the new key (count 1) may be evicted immediately.
• Empty buckets. Delete a bucket when it empties, or minf logic and memory both go wrong.

Related problems

• LRU Cache (LeetCode 146): the simpler sibling: evict purely by recency with a map and a linked list.
• Insert Delete GetRandom O(1) (LeetCode 380): another design where two structures must stay in sync on every call.
• Design HashMap (LeetCode 706): the hash table underneath every O(1) lookup used here.