Introduction

An LFU cache evicts the key that has been used the fewest times. To make that practical, the cache must update frequency counts quickly and still support fast get and put operations.

What an LFU Cache Needs to Track

A usable LFU cache needs more than a dictionary of key-value pairs. It must track:

• the value for each key
• the access frequency for each key
• which keys share the same frequency
• the current minimum frequency in the cache

If you only store a counter per key and scan the whole cache on eviction, the algorithm becomes too slow.

The standard approach is:

• a map from key to node data
• a map from frequency to an ordered bucket of keys
• a min_freq value so eviction knows where to look first

When multiple keys have the same frequency, many implementations evict the least recently used key among that frequency bucket.

Python Implementation

The following implementation uses OrderedDict to keep insertion order inside each frequency bucket.

1from collections import defaultdict, OrderedDict
2
3
4class LFUCache:
5    def __init__(self, capacity):
6        self.capacity = capacity
7        self.size = 0
8        self.min_freq = 0
9        self.key_to_value_freq = {}
10        self.freq_to_keys = defaultdict(OrderedDict)
11
12    def _touch(self, key):
13        value, freq = self.key_to_value_freq[key]
14
15        del self.freq_to_keys[freq][key]
16        if not self.freq_to_keys[freq]:
17            del self.freq_to_keys[freq]
18            if self.min_freq == freq:
19                self.min_freq += 1
20
21        new_freq = freq + 1
22        self.key_to_value_freq[key] = (value, new_freq)
23        self.freq_to_keys[new_freq][key] = None
24
25    def get(self, key):
26        if key not in self.key_to_value_freq:
27            return -1
28
29        value, _ = self.key_to_value_freq[key]
30        self._touch(key)
31        return value
32
33    def put(self, key, value):
34        if self.capacity == 0:
35            return
36
37        if key in self.key_to_value_freq:
38            _, freq = self.key_to_value_freq[key]
39            self.key_to_value_freq[key] = (value, freq)
40            self._touch(key)
41            return
42
43        if self.size == self.capacity:
44            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
45            del self.key_to_value_freq[evict_key]
46            if not self.freq_to_keys[self.min_freq]:
47                del self.freq_to_keys[self.min_freq]
48            self.size -= 1
49
50        self.key_to_value_freq[key] = (value, 1)
51        self.freq_to_keys[1][key] = None
52        self.min_freq = 1
53        self.size += 1
54
55
56cache = LFUCache(2)
57cache.put(1, "A")
58cache.put(2, "B")
59print(cache.get(1))   # A, freq of key 1 becomes 2
60cache.put(3, "C")     # evicts key 2
61print(cache.get(2))   # -1
62print(cache.get(3))   # C

This design gives amortized O(1) operations for the typical interview-style LFU cache API.

How the Eviction Rule Works

Suppose the cache contains:

• key 1 with frequency 3
• key 2 with frequency 1
• key 3 with frequency 1

If the cache is full and a new key arrives, the eviction must come from the minimum-frequency bucket, which is frequency 1. If multiple keys share that bucket, the oldest one in that bucket is removed first.

That tie-breaker is important because otherwise LFU alone is ambiguous.

Why min_freq Matters

Without min_freq, eviction would require scanning all frequencies to find the smallest one still in use. That would destroy performance.

By updating min_freq every time a key changes buckets, the cache always knows where the current eviction candidate lives.

This is the subtle part of the implementation:

• insert new key, set min_freq = 1
• move key from one bucket to the next on every access
• if a frequency bucket becomes empty and it was the minimum, increment min_freq

If that bookkeeping is wrong, the cache will evict the wrong item even if the rest of the data structure looks fine.

When LFU Is a Good Choice

LFU works best when long-term popularity matters more than short-term recency. For example, if a small set of keys is accessed repeatedly over time, LFU tends to protect them better than LRU.

On the other hand, LFU can be a poor fit when access patterns shift quickly. A key that was hot in the past can keep an artificially high frequency and resist eviction longer than it should.

That tradeoff is why real systems sometimes use approximate LFU or hybrid policies instead of a strict textbook implementation.

Common Pitfalls

Updating the frequency counter on put for an existing key but forgetting to move the key to the next frequency bucket makes the internal state inconsistent.

Evicting from the global oldest key instead of the oldest key in the minimum-frequency bucket changes the policy from LFU-with-LRU-tiebreak to something else.

Forgetting to reset min_freq to 1 when inserting a fresh key after eviction causes later evictions to look in the wrong bucket.

Ignoring the capacity-zero case leads to awkward bugs where the cache appears to accept writes but cannot actually store anything.

Summary

• An LFU cache tracks values, frequencies, and the current minimum frequency.
• Efficient implementations use a key map plus per-frequency ordered buckets.
• 'min_freq is what keeps eviction fast.'
• When frequencies tie, evicting the least recently used key within that bucket is a practical rule.
• The hardest part is not storing counts, but keeping bucket transitions and min_freq correct.