LFU Cache

Design a Least Frequently Used (LFU) cache. When capacity is exceeded, evict the LFU item (if tie, evict LRU among them).

Example 1

LFUCache(2), put(1,1), put(2,2), get(1)→1, put(3,3) [evicts 2], get(2)→-1, get(3)→3

Solution Approach

Two HashMaps + HashMap of LinkedHashSets. keyMap(key→val,freq), freqMap(freq→orderedSet of keys), minFreq.

keyMap: key → [val, freq].
freqMap: freq → LinkedHashSet (insertion-ordered for LRU within freq).
minFreq: tracks current minimum frequency.
On get: update freq, move key in freqMap. On put: evict minFreq first from freqMap[minFreq].

Java

import java.util.*;

class LFUCache {
    Map<Integer,int[]> keyMap = new HashMap<>(); // key -> [val, freq]
    Map<Integer,LinkedHashSet<Integer>> freqMap = new HashMap<>();
    int cap, minFreq;

    public LFUCache(int capacity) { cap=capacity; }
    private void updateFreq(int key) {
        int freq = keyMap.get(key)[1];
        freqMap.get(freq).remove(key);
        if (freqMap.get(freq).isEmpty()) { freqMap.remove(freq); if (minFreq==freq) minFreq++; }
        keyMap.get(key)[1]++;
        freqMap.computeIfAbsent(freq+1, k->new LinkedHashSet<>()).add(key);
    }
    public int get(int key) {
        if (!keyMap.containsKey(key)) return -1;
        updateFreq(key); return keyMap.get(key)[0];
    }
    public void put(int key, int value) {
        if (cap <= 0) return;
        if (keyMap.containsKey(key)) { keyMap.get(key)[0]=value; updateFreq(key); return; }
        if (keyMap.size() >= cap) {
            int evict = freqMap.get(minFreq).iterator().next();
            freqMap.get(minFreq).remove(evict); if(freqMap.get(minFreq).isEmpty()) freqMap.remove(minFreq);
            keyMap.remove(evict);
        }
        keyMap.put(key, new int[]{value,1});
        freqMap.computeIfAbsent(1, k->new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
}

Time Complexity: get/put: O(1)
Space Complexity: O(N)