DSA problem
LFU Cache
Design a Least Frequently Used (LFU) cache with O(1) average time for both get and put. The cache holds at most capacity key-value pairs. get(key) returns the value if present and increments that key's use count, otherwise returns -1. put(key, value) inserts or updates the key, increments its use count, and on overflow evicts the key with the smallest use count, breaking ties by least-recently-used among equally-infrequent keys.
The key insight: maintain one doubly-linked list per frequency, where within a list, nodes are ordered by recency (most recent at the head, least recent at the tail). Combine this with a hash map from key to node and another hash map from frequency to its list. Track minFreq — the smallest frequency that currently has any entries — to make eviction O(1).
get(key) looks up the node, unlinks it from its current frequency list, increments its frequency, and appends it to the head of the new frequency list. If its old list becomes empty and equals minFreq, bump minFreq. put(key, value) either updates and bumps frequency like get, or — for a new key — checks capacity and possibly evicts the tail of the minFreq list (which is the LFU + LRU candidate). New keys start at frequency 1, so minFreq is reset to 1.
Every linked-list operation is O(1) because we always hold a direct node pointer. Every hash-map operation is O(1) average. The clever bit is the minFreq invariant: whenever a node moves up in frequency or a new node arrives at frequency 1, minFreq can only stay the same or move to 1 or the next-existing frequency — never a hard search. This is the canonical interview-grade LFU.
Examples
LFUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); get(3)[1, -1, 3]LFUCache(2); put(1,1); put(2,2); get(1); get(2); put(3,3); get(1)[1, 2, 1]LFUCache(1); put(1,1); put(2,2); get(1)-1Constraints
- 1 <= capacity <= 10^4
- 0 <= key <= 10^5
- 0 <= value <= 10^9
- At most 2 * 10^5 calls will be made to get and put.
- Both get and put must run in O(1) average time complexity.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.