LFU Cache

Share

Design an LFU (Least Frequently Used) cache. On eviction, remove the least frequently used item; if tie, remove the least recently used among them. Implement get and put in O(1).

Example 1
Input: ["LFUCache","put","put","get","put","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[3]]
Output: [null,null,null,1,null,-1,3]
Explanation: key=2 is evicted (freq=1) when key=3 is put; cap=2.
Example 2
Input: capacity=1; put(1,1); put(2,2); get(1)→-1; get(2)→2
Output:

Solution Approach

Three data structures: keyMap(key→{val,freq}), freqMap(freq→LinkedHashSet of keys), and minFreq tracker.

  • get: increment key frequency, update freqMap, update minFreq
  • put: if capacity exceeded evict minFreq entry, then insert with freq=1
Java
class LFUCache {
    Map<Integer,Integer> keyVal = new HashMap<>(), keyFreq = new HashMap<>();
    Map<Integer,LinkedHashSet<Integer>> freqKeys = new HashMap<>();
    int cap, minFreq = 0;
    public LFUCache(int capacity) { cap = capacity; }
    public int get(int key) {
        if (!keyVal.containsKey(key)) return -1;
        int f = keyFreq.get(key);
        keyFreq.put(key, f+1);
        freqKeys.get(f).remove(key);
        if (freqKeys.get(f).isEmpty()) { freqKeys.remove(f); if (minFreq==f) minFreq++; }
        freqKeys.computeIfAbsent(f+1, x->new LinkedHashSet<>()).add(key);
        return keyVal.get(key);
    }
    public void put(int key, int value) {
        if (cap <= 0) return;
        if (keyVal.containsKey(key)) { keyVal.put(key,value); get(key); return; }
        if (keyVal.size() >= cap) {
            int evict = freqKeys.get(minFreq).iterator().next();
            freqKeys.get(minFreq).remove(evict);
            keyVal.remove(evict); keyFreq.remove(evict);
        }
        keyVal.put(key,value); keyFreq.put(key,1);
        freqKeys.computeIfAbsent(1, x->new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
}
Complexity Analysis:

Time complexity: O(1) for get and put
Space complexity: O(capacity)