LFU Cache
hardTime: O(1)Space: O(capacity)
Recognize the pattern
evict least frequently used on capacity overflowO(1) get and puttrack frequency AND recency
Brute force idea
Scan all entries for minimum frequency on eviction — O(n) per put.
Better approach
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).
Key invariant
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.
Watch out for
Not resetting minFreq on new key insertion — new keys always enter at freq=1, so minFreq resets to 1 on every new key.