visual walkthrough
LFU Cache
An LRU follow-up with frequency buckets.
The idea
LFU evicts the key used the fewest times, and on a tie the one used longest ago. So keys are ordered by use count first, then by recency.
Keep one recency list per use count (like an LRU per bucket) and remember the smallest count in use. The victim is always the oldest key in that bucket.
Complexity
| approach | time | space |
|---|---|---|
| Counts and timestamps | O(n) per eviction | O(n) |
| Frequency buckets | O(1) per op | O(capacity) |