4.9.12 — LFU Cache

LeetCode 460 · Hard · beyond the NeetCode 150, and the standard follow-up to 4.9.9 LRU Cache

The problem

Design a cache with a fixed capacity supporting two operations, both in O(1) on average:

• get(key) — return the value, or −1 if absent. This counts as using the key.
• put(key, value) — insert or update; an update also counts as a use. If a new key would take the cache over capacity, first evict the least frequently used key. If several keys share the lowest use count, evict the one among them that was used least recently.

LFUCache(2)
put(1,1); put(2,2)
get(1)      → 1        (key 1 used twice now, key 2 once)
put(3,3)               (full: evict key 2, the only key with count 1)
get(2)      → -1
get(3)      → 3        (keys 1 and 3 both have count 2)
put(4,4)               (full: tie at count 2, so evict key 1, used longer ago than key 3)
get(1)      → -1
get(3)      → 3
get(4)      → 4

What this problem is really asking

LRU asked "which key was touched longest ago?". LFU asks "which key has been touched the fewest times, and among those, longest ago?". That is two orderings at once, and both must be maintained in constant time on every single call.

Constraints to note:

• capacity is up to 10^4, keys up to 10^5, values up to 10^9.
• Up to 2 \times 10^5 calls in total.
• capacity can be 0, in which case nothing is ever stored.

The brute force, and its waste

Keep a hash map from key to (value, count, last-used time), and on eviction scan every key for the smallest (count, last-used time). The waste: every eviction re-examines all keys to find one minimum that barely changed since the last eviction. With a full cache of 10^4 keys and up to 2 \times 10^5 calls, that is up to 2 \times 10^9 comparisons, far over any time limit.

A heap ordered by (count, time) looks like the fix, but every get changes a key's count, and changing a priority in the middle of a heap costs O(\log n). That is acceptable in practice and is still not the O(1) the problem demands.

The idea

Group the keys by their use count. Each group is a small LRU list of the keys that have exactly that count, oldest first.

• To evict: go to the group with the smallest count and remove its oldest key.
• To use a key: take it out of group f and add it to the back of group f + 1.

Both are constant-time, provided you can find "the group with the smallest count" without searching. That is the one clever part: keep a single number, min_freq, and notice that it only ever changes in two simple ways.

1. When a new key is inserted, min_freq becomes 1. A brand-new key has been used once, and nothing can have fewer than one use.
2. When a key moves from group f to f + 1 and group f becomes empty, min_freq goes up by exactly one, if it was f. The key that just moved is now in group f + 1, so that group cannot be empty.

So min_freq never needs a search. That observation is the whole difference between O(1) and O(\log n).

The solution

Python

from collections import defaultdict, OrderedDict


class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.val = {}                                   # (1) key → value
        self.freq = {}                                  #     key → how many times it was used
        self.buckets = defaultdict(OrderedDict)         # (2) use count → keys with that count, oldest first
        self.min_freq = 0                               # (3) smallest use count in the cache

    def _touch(self, key: int) -> None:                 # (4) move key from bucket f to bucket f + 1
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1                   # (5)
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None

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

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:                               # (6)
            return
        if key in self.val:
            self.val[key] = value
            self._touch(key)                            # an update counts as a use
            return
        if len(self.val) == self.cap:
            evict, _ = self.buckets[self.min_freq].popitem(last=False)   # (7)
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.val[evict], self.freq[evict]
        self.val[key] = value                           # (8)
        self.freq[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1

TypeScript

class LFUCache {
  private vals = new Map<number, number>();               // (1) key → value
  private freq = new Map<number, number>();               //     key → how many times it was used
  private buckets = new Map<number, Set<number>>();       // (2) use count → keys, oldest first
  private minFreq = 0;                                    // (3)

  constructor(private readonly cap: number) {}

  private touch(key: number): void {                      // (4)
    const f = this.freq.get(key)!;
    const bucket = this.buckets.get(f)!;
    bucket.delete(key);
    if (bucket.size === 0) {
      this.buckets.delete(f);
      if (this.minFreq === f) this.minFreq = f + 1;       // (5)
    }
    this.freq.set(key, f + 1);
    if (!this.buckets.has(f + 1)) this.buckets.set(f + 1, new Set());
    this.buckets.get(f + 1)!.add(key);
  }

  get(key: number): number {
    if (!this.vals.has(key)) return -1;
    this.touch(key);
    return this.vals.get(key)!;
  }

  put(key: number, value: number): void {
    if (this.cap === 0) return;                           // (6)
    if (this.vals.has(key)) {
      this.vals.set(key, value);
      this.touch(key);                                    // an update counts as a use
      return;
    }
    if (this.vals.size === this.cap) {
      const bucket = this.buckets.get(this.minFreq)!;
      const evict = bucket.values().next().value!;        // (7) oldest key in the lowest bucket
      bucket.delete(evict);
      if (bucket.size === 0) this.buckets.delete(this.minFreq);
      this.vals.delete(evict);
      this.freq.delete(evict);
    }
    this.vals.set(key, value);                            // (8)
    this.freq.set(key, 1);
    if (!this.buckets.has(1)) this.buckets.set(1, new Set());
    this.buckets.get(1)!.add(key);
    this.minFreq = 1;
  }
}

1. Two plain maps record each key's value and how many times it has been used.
2. The groups. buckets[f] holds the keys used exactly f times, in the order they arrived in that group, so the first one is the least recently used. Python's OrderedDict and JavaScript's Set both remember insertion order and both delete any member in O(1), which is exactly the job the doubly linked list did in LRU.
3. The smallest count present in the cache, maintained by the two rules above.
4. _touch is the only place a count changes. It removes the key from its current group, adds it to the end of the next one, and tidies up.
5. Rule 2 from the idea, in one line. Note it is f + 1, not "search for the next non-empty group": the key being moved guarantees that group exists.
6. Capacity 0 is a real test case. Without this line, the eviction step below would try to evict from an empty cache and crash.
7. Evict the first key in the lowest group. It has the fewest uses, and among keys with that count it is the one that reached the count longest ago, which is the tie-break the problem asks for. Python's popitem(last=False) removes the oldest entry; in TypeScript, values().next().value reads it and delete removes it.
8. A new key starts with one use in group 1, and rule 1 sets min_freq to 1. This happens after the eviction on purpose: the eviction needed the old min_freq.

Where the languages differ. In Python a missing group is created automatically by defaultdict; in TypeScript the code must create the Set itself before adding to it. Also, re-adding a key that is already in a JavaScript Set does not move it to the end; that is why touch always deletes from one group and adds to a different one, never re-adds to the same group.

Hand trace

The example above, with the groups written as count: [keys, oldest first]:

Call	Returns	Groups after the call	min_freq
put(1,1)		1: [1]	1
put(2,2)		1: [1, 2]	1
get(1)	1	1: [2], 2: [1]	1
put(3,3)		1: [3], 2: [1] (evicted 2)	1
get(2)	−1	unchanged	1
get(3)	3	2: [1, 3] (group 1 emptied)	2
put(4,4)		1: [4], 2: [3] (evicted 1)	1
get(1)	−1	unchanged	1
get(3)	3	1: [4], 3: [3]	1
get(4)	4	2: [4], 3: [3]	2

Two rows carry the lesson. In the get(3) row, group 1 becomes empty while min_freq was 1, so rule 2 moves it to 2 without searching, and group 2 indeed holds keys. In the put(4,4) row, keys 1 and 3 both have count 2; key 1 entered group 2 before key 3 did, so it is first in the group and is the one evicted.

Both versions were checked against a slow reference implementation (the brute force above) on 2,000 random sequences of 200 calls each, with capacities from 0 to 5; every get agreed.

Complexity

Time: O(1) on average for both operations. Count the work in each call. get does a map lookup and, through _touch, a fixed number of map and ordered-set operations: one delete from a group, possibly one group deletion, one insert into the next group. Each is O(1) on average because they are hash-based. put does at most one eviction (one removal from the front of one group plus two map deletions) and one insertion. Nothing loops over keys or groups, and min_freq is updated by assignment, never by a search.

Space: O(\text{capacity}). Every stored key appears exactly once in each of the two maps and in exactly one group, and there are never more non-empty groups than keys.

Edge cases

• Capacity 0: every put is ignored and every get returns −1.
• put on an existing key updates the value and counts as a use. Forgetting the second half is the most common wrong answer, because the problem statement mentions it only once.
• Ties on the lowest count are broken by recency within the group, which the ordered group gives for free.
• An evicted key that comes back starts again at a count of 1. LFU forgets everything about a key once it is evicted.

Variations you will meet

• LRU Cache (4.9.9) is this problem with a single group: recency only.
• Writing the groups by hand. An interviewer may forbid OrderedDict. Then each group is its own doubly linked list with a dummy head and tail, exactly as in LRU, plus a map from count to that list. The logic above does not change.
• Real LFU caches age their counts. A key that was popular last month and is never read now would otherwise stay forever. Redis, for example, offers an LFU eviction mode whose per-key counter is approximate and decays over time, which is cheaper than exact counts and forgets old popularity. 10.14.1 compares eviction policies.

The generalisation is the same as LRU's, one level up: when the eviction rule needs two orderings, group by the first, keep each group ordered by the second, and track the smallest group with a number that only changes in predictable ways.

What the interviewer will push on

"Why not a heap?" They are checking whether you see that a get changes a key's priority. A heap can handle that, but only in O(\log n), and only if you can find the key inside the heap. The strong answer names that cost and then shows why frequency groups avoid it. A weak answer says "heaps are slow".

"How do you find the minimum frequency in O(1)?" The tell of real understanding is the two rules: a new key resets it to 1, and emptying the minimum group by moving a key up raises it by exactly one. Candidates who say "scan the buckets" have quietly made eviction O(n).

"Does put on an existing key change its frequency?" Yes, and many solutions fail exactly here. It is worth saying unprompted, because it shows you read the specification rather than assuming.

"What happens with capacity 0?" Without a guard, the eviction path runs on an empty cache. Naming the guard before writing it reads as experience.

"Is LFU better than LRU?" Neither is better in general. LFU keeps steadily popular items through a burst of one-off reads that would flush an LRU cache, but it holds on to formerly popular items too long unless counts decay. Saying when each wins, rather than ranking them, is what the interviewer wants to hear.

One thing to volunteer: before coding, say the invariant aloud: "Every key is in exactly one group, the group for its use count; each group is in recency order; and min_freq is the smallest non-empty group, which I update in two places only." Everything in the code maintains that sentence.

Next: 4.10 goes back to a single array and asks how it gets sorted and searched, including binary search stated in the form that generalises far beyond sorted arrays.