LFU Cache
Hard Frequency buckets of LinkedHashSets
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design a cache with get and put in O(1). When full, evict the key used least often; among ties, evict the least recently used one.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: evict the least frequently used key; break ties by least recently used.
Why this works: group keys by use count, each group in insertion order (LinkedHashSet). Track the smallest count so eviction is O(1).
Example: capacity 2: put 1, put 2, get 1, put 3
counts: 1→2, 2→1put 3 evicts key 2 (lowest count)
✦Hints open one at a time
↗Approach
Maps: key → value, key → count, count → LinkedHashSet of keys. Touching a key moves it from bucket c to c + 1 (and bumps minCount if bucket c emptied and c was the minimum). Evict the first key in bucket minCount.
</>Solution (Java)
import java.util.*;
class LFUCache {
private final int capacity;
private int minCount = 0;
private final Map<Integer, Integer> vals = new HashMap<>(), counts = new HashMap<>();
private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>();
public LFUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!vals.containsKey(key)) return -1;
touch(key);
return vals.get(key);
}
public void put(int key, int value) {
if (capacity == 0) return;
if (vals.containsKey(key)) {
vals.put(key, value);
touch(key);
return;
}
if (vals.size() == capacity) {
int evict = buckets.get(minCount).iterator().next(); // oldest among least used
buckets.get(minCount).remove(evict);
vals.remove(evict);
counts.remove(evict);
}
vals.put(key, value);
counts.put(key, 1);
buckets.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
minCount = 1;
}
private void touch(int key) {
int c = counts.get(key);
counts.put(key, c + 1);
buckets.get(c).remove(key);
if (c == minCount && buckets.get(c).isEmpty()) minCount++;
buckets.computeIfAbsent(c + 1, k -> new LinkedHashSet<>()).add(key);
}
}!Common mistake
Forgetting that minCount can only increase by touching keys and resets to 1 on every new insert.
- Time: O(1) average per operation.
- Space: O(capacity).