SpecializedData structureaka least frequently used cache

LFU Cache

A fixed-capacity cache that evicts the entry with the lowest access count (ties broken by least recent), in O(1) using a map of frequency buckets.

Pattern: HashingPractice (3)
Progress

Definition

An LFU cache evicts the key that has been accessed the fewest times; when several keys tie, the least recently used among them goes. It rewards keys that are hot over the long term, resisting the scan pollution that hurts an LRU Cache.

The O(1) design keeps three structures: keyToNode (key → node with value and frequency), freqToList (frequency → doubly linked list of nodes in LRU order), and minFreq (the smallest frequency currently present). Every access removes the node from its current frequency list and appends it to the list for freq + 1; eviction pops the LRU end of freqToList[minFreq].

The subtlety is minFreq maintenance: after a get/put on an existing key, if the old list became empty and it was minFreq, increment minFreq. After inserting a brand-new key, minFreq is always 1.

cache evictionfrequency bucketsO(1) get/putdesignhash map + linked lists

Intuition

A mental model before the formal terms.

A library sorts books onto shelves by how many times they have been checked out: shelf 1, shelf 2, shelf 3, … Each checkout moves the book one shelf up, placing it at the "newest" end of that shelf. When space runs out, the librarian goes to the lowest non-empty shelf and removes the book that has been sitting there the longest. A catalogue card (hash map) records which shelf and position every book is on, so no searching is needed.

How it works

  1. Node: key, value, freq, prev, next. Bucket: a doubly linked list with sentinels for one frequency.
  2. get(key): if absent → miss. Otherwise touch(node) and return the value.
  3. touch(node): unlink from freqToList[node.freq]; if that list is now empty and node.freq == minFreq, minFreq++; node.freq++; append to the front (MRU end) of freqToList[node.freq], creating the bucket if needed.
  4. put(key, value): if the key exists, set the value and touch. Otherwise, if at capacity, evict: take the tail (LRU) node of freqToList[minFreq], unlink it, delete from keyToNode. Then create a node with freq = 1, insert into bucket 1, set minFreq = 1.
  5. Delete empty buckets from freqToList (or leave them; both are correct if minFreq logic checks for emptiness).

Why it works

Each bucket is ordered by recency, so within a frequency the tail is the LRU — giving the required tiebreak.

minFreq can only rise by exactly one after an access (the touched node moves from f to f + 1, and only if bucket f was minFreq and is now empty) or reset to 1 on insertion, so it is maintained in O(1) without scanning.

All list operations are pointer swaps with sentinels; all map operations are O(1) average.

Operations

OperationDescriptionCost
get(key)Lookup; move node to the next frequency bucket.O(1)
put(key, value)Insert with freq 1 or update; evict LRU of minFreq bucket if full.O(1)
evict()Pop tail of freqToList[minFreq].O(1)
frequency(key)Read node.freq.O(1)

Recognition

How to tell a problem wants this.

  • "Evict the least frequently used", "count accesses", "ties broken by recency".
  • Follow-up to the LRU design question.
  • Workloads where a few keys are accessed far more than the rest and should never be evicted by a one-off scan.
“have you seen this before” → Hashing“reverse a linked list” → Linked List Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1get(k): if k not in nodes: return -1; touch(nodes[k]); return value
2touch(n): remove n from bucket[n.freq]; if bucket empty and n.freq == minFreq: minFreq += 1
3         n.freq += 1; push n to front of bucket[n.freq]
4put(k, v): if k in nodes: update, touch; return
5  if size == cap: victim = tail of bucket[minFreq]; remove; delete nodes[victim.key]
6  n = Node(k, v, freq=1); push front of bucket[1]; nodes[k] = n; minFreq = 1

Implementation

1from collections import defaultdict
2from typing import Generic, Hashable, Optional, TypeVar
3 
4K = TypeVar("K", bound=Hashable)
5V = TypeVar("V")
6 
7 
8class _Entry(Generic[V]):
9    __slots__ = ("val", "freq")
10 
11    def __init__(self, val: V):
12        self.val = val
13        self.freq = 1
14 
15 
16class LFUCache(Generic[K, V]):
171 · State — key→entry map, frequency buckets (front = most recent), minFreq
18    def __init__(self, capacity: int):
19        self.cap = capacity
20        self.entries: dict[K, _Entry[V]] = {}
21        # freq -> insertion-ordered dict used as an ordered set (first key = least recent)
22        self.buckets: defaultdict[int, dict[K, None]] = defaultdict(dict)
23        self.min_freq = 0
24 
252 · touch — move an entry to the next frequency bucket
26    def _touch(self, key: K, e: _Entry[V]) -> None:
27        bucket = self.buckets[e.freq]
28        del bucket[key]
29        if not bucket:
30            del self.buckets[e.freq]
31            if self.min_freq == e.freq:
32                self.min_freq += 1  # min_freq can only rise by exactly one
33        e.freq += 1
34        self.buckets[e.freq][key] = None  # appended -> most recent in its bucket
35 
363 · get — look up and touch
37    def get(self, key: K) -> Optional[V]:
38        e = self.entries.get(key)
39        if e is None:
40            return None
41        self._touch(key, e)
42        return e.val
43 
444 · put — update existing, or evict LRU of the minFreq bucket and insert at freq 1
45    def put(self, key: K, val: V) -> None:
46        if self.cap == 0:
47            return
48        e = self.entries.get(key)
49        if e is not None:
50            e.val = val
51            self._touch(key, e)
52            return
53        if len(self.entries) >= self.cap:  # evict BEFORE inserting the new key
54            bucket = self.buckets[self.min_freq]
55            victim = next(iter(bucket))  # first inserted = least recent
56            del bucket[victim]
57            if not bucket:
58                del self.buckets[self.min_freq]
59            del self.entries[victim]
60        self.entries[key] = _Entry(val)
61        self.buckets[1][key] = None
62        self.min_freq = 1
63 
645 · Size
65    def __len__(self) -> int:
66        return len(self.entries)
Walkthrough
  1. Buckets are plain dicts used as ordered sets (dict[K, None]): insertion order is guaranteed, deletion anywhere is O(1), and next(iter(bucket)) yields the oldest key — the LRU victim within a frequency.
  2. _touch removes the key from its old bucket, deletes the bucket if it emptied (bumping min_freq if it was the minimum), then appends the key to the bucket for freq + 1 via defaultdict.
  3. get returns None on a miss; otherwise it touches the entry and returns e.val.
  4. put at capacity picks next(iter(self.buckets[self.min_freq])), deletes it from both structures, then inserts the new _Entry at frequency 1 and sets min_freq = 1.
  5. _Entry uses __slots__ to keep the per-key overhead at two attributes.
Complexity (this implementation)
time O(1) per get/put · space O(capacity)

One dict per distinct frequency in use; empty buckets are deleted eagerly.

Language notes
  • A dict[K, None] is the standard ordered-set idiom — set iterates in arbitrary order, so it cannot break frequency ties by recency.
  • defaultdict(dict) auto-creates a bucket on first append; the explicit del self.buckets[...] calls keep empty buckets from lingering (and from making min_freq point at an empty dict).
  • Unlike LRU, no stdlib type implements LFU for you — OrderedDict gives recency, not frequency; this composition of dicts is the idiomatic build.
  • next(iter(d)) is O(1); list(d)[0] copies the whole bucket.
Common mistakes in this language
  • Using set for buckets — arbitrary iteration order breaks the recency tiebreak.
  • Evicting after inserting the new key, which can evict the key just added.
  • Reading self.buckets[self.min_freq] through the defaultdict after forgetting to delete an empty bucket — it silently returns {} and next(iter(...)) raises StopIteration.
  • Forgetting self.min_freq = 1 on insert.
Language differences that matter here
  • The recency list inside each bucket: C++ uses std::list<K> with stored iterators; JS/TS exploit insertion-ordered Set; Python uses a dict[K, None] as an ordered set — set itself is unordered and would break the tiebreak.
  • Miss signalling: C++ std::optional<V>, TS V | undefined, Python None, JS -1 (the LeetCode contract).
  • C++ entries.emplace sidesteps operator[]'s requirement that the value type be default-constructible — no analogue exists (or is needed) in the other languages.
  • No language has LFU in its standard library (unlike LRU in Python); all four compose it from maps plus an ordered per-frequency structure.

Complexity

OperationAverageWorstNote
AccessO(1)O(1)By key.
SearchO(1)O(n)Hash-map worst case.
InsertO(1)O(1)
DeleteO(1)O(1)Eviction.
UpdateO(1)O(1)
GetO(1)O(1)
PutO(1)O(1)
EvictO(1)O(1)
SpaceO(capacity)Plus one bucket header per distinct frequency in use.

Advantages & disadvantages

Advantages
  • Keeps long-term hot keys resident regardless of transient scans.
  • O(1) for every operation with the bucket design.
  • Provides access counts as a by-product.
Disadvantages
  • More code and memory than LRU: a second map and one list per frequency.
  • Stale popularity: a key that was hot last week keeps a high count and is hard to evict (mitigated by aging/decay, which complicates the O(1) design).
  • New keys enter at frequency 1 and are evicted first, so bursty new working sets struggle to get in.

Use cases

  • CDN and object caches with stable popularity distributions.
  • Database block caches (with aging) and JIT compilers deciding what to keep compiled.
  • Interview design question LFU Cache (LeetCode 460).
Use it when
  • Popularity is skewed and stable; hot keys should survive scans.
  • The interviewer asks for LFU with O(1) operations.
Avoid it when
  • Recency is the better predictor (most workloads) — LRU Cache is simpler and often hits more.
  • Popularity shifts over time and you cannot afford aging logic.
  • Capacity is tiny; the extra structures outweigh the benefit.

Alternatives

LRU CacheHash MapMin-Heap

Common mistakes

  • Using a Min-Heap keyed on frequency — O(log n) per operation and awkward recency tiebreaks.
  • Not resetting minFreq = 1 after inserting a new key.
  • Incrementing minFreq when the old bucket is empty even if it was not the minFreq bucket.
  • Evicting from the head (MRU) end of the bucket instead of the tail (LRU).
  • Forgetting the capacity == 0 edge case.
  • Evicting *after* inserting the new key, which can evict the key just added.

Interview patterns

  • LFU Cache (LeetCode 460): the bucket-of-lists design above.
  • Compare LRU vs LFU behaviour on a scan followed by a hot-key workload.
  • Discuss aging/decay and approximate LFU (TinyLFU, count-min sketches).
Interview questions on this
Mock interviews

Interview problems

Design HashMapeasyLRU CachemediumTop K Frequent Elementsmedium