Problem Statement

LFU Cache

We are building a cache. A cache is a small box that holds a limited number of items so we can grab them fast. This one is an LFU cache, which stands for Least Frequently Used. The rule is simple: when the box is full and we need room for something new, we throw out the item that has been used the fewest times. "Used" means asked for or set. If two items are tied for fewest uses, we throw out the one we have not touched in the longest time. The catch is that every action has to be fast, O(1), which means the work does not grow when the cache grows. To pull that off we keep three lookup tables side by side: one from each key to its value, one from each key to how many times it has been used, and one from each use-count to the list of keys that currently sit at that count. A lookup table (a map or dictionary) is like a coat-check: you hand over a tag and instantly get back the matching coat, no searching.

hardDesignHash TableArrays & HashingTime: O(1) · Space: O(capacity)

Signals to notice

evict least frequently used on capacity overflowO(1) get and puttrack frequency AND recency

Brute force first

Scan all entries for minimum frequency on eviction — O(n) per put.

The key insight

Hash map (key → node) + frequency buckets (freq → doubly linked list). Track minFreq. On access, promote node to freq+1. On eviction, remove LRU from minFreq bucket. All O(1).

Trace it on `cap=2; put(1,1) put(2,2) get(1) put(3,3) get(2) get(1) put(4,4)`

put(1,1): new -> val{1:1} freq{1:1} bucket{1:[1]} minFreq=1
put(2,2): new, room -> val{1:1,2:2} bucket{1:[1,2]} minFreq=1
get(1)->1: promote 1 to freq2 -> bucket{1:[2],2:[1]} minFreq stays 1
put(3,3): full -> evict bucket[minFreq=1] LRU = key 2 -> bucket{1:[3],2:[1]} minFreq=1
get(2)->-1: not in cache, no change
get(1)->1: promote 1 to freq3 -> bucket{1:[3],3:[1]} minFreq=1
put(4,4): full -> evict bucket[1] LRU = key 3 -> val{1:1,4:4} bucket{1:[4],3:[1]} minFreq=1

What must stay true

Each frequency level has its own LRU list. minFreq points to the lowest non-empty bucket. Eviction removes the LRU from that bucket — least frequent, and among those, least recently used.

Shape of the loop

_update(key):              # called on every access
  f = keyFreq[key]; keyFreq[key] = f+1
  freqKeys[f].remove(key)   # LRU-ordered bucket
  if freqKeys[f] empty and f == minFreq: minFreq += 1
  freqKeys[f+1].add(key)    # promote to next bucket
put(key,val): if full -> evict freqKeys[minFreq].popLRU(); insert at freq 1; minFreq = 1

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not resetting minFreq on new key insertion — new keys always enter at freq=1, so minFreq resets to 1 on every new key.

Arrays & Hashing Pattern