370. LFU Cache
Design a cache that evicts the least frequently used entry when it runs out of room.
Implement a class LFUCache:
LFUCache(capacity)— creates a cache holding at mostcapacitykey–value pairs.get(key)— returns the value stored underkey, or-1if the key is absent.put(key, value)— storesvalueunderkey, overwriting any existing value. If the key is new and the cache is already full, first evict the key with the lowest use count; if several keys tie for the lowest count, evict the least recently used among them.
Every get of a present key and every put on a key (insert or overwrite) counts as one use of that key; a freshly inserted key starts at use count 1. Aim for O(1) average time per operation.
Example 1:
Input: LFUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); get(3); put(4,4); get(1); get(3); get(4)
Output: [1, -1, 3, -1, 3, 4]
Explanation: put 3 must evict: key 2 has use count 1 (one put) while key 1 has 2 (put + get), so key 2 goes. put 4 faces a tie — keys 1 and 3 both have count 2 — and evicts key 1, the least recently touched of the two.
Example 2:
Input: LFUCache(1); put(1,1); get(1); put(2,2); get(1); get(2)
Output: [1, -1, 2]
Explanation: With room for a single entry, inserting key 2 must evict key 1 — it is the only occupant, so its higher use count offers no protection.
Constraints:
- 0 ≤ capacity ≤ 10⁴
- 0 ≤ key, value ≤ 10⁹
- 1 ≤ number of operations ≤ 10⁵
- There is at least one get operation.
Hints:
A single hash map from key to (value, count) finds entries in O(1), but eviction then needs a scan for the smallest count. Start there — it is correct, just slow.
Group keys by use count: one bucket per count, each bucket ordered by recency (an ordered dict / linked hash set). Moving a key from bucket f to bucket f+1 is an O(1) unlink + append.
Track minFreq, the lowest count currently present. It only ever resets to 1 (on a fresh insert) or increases by exactly 1 (when the bucket it points at empties during a touch) — eviction always pops the oldest key of bucket minFreq.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: LFUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); get(3); put(4,4); get(1); get(3); get(4)
Expected output: [1, -1, 3, -1, 3, 4]