LFU Cache
hardTime: 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).
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.
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.