255. LFU Cache

Group keys by their use count into buckets, each an LRU-ordered list. Track the minimum frequency so eviction and every access stay O(1).

Buckets by frequency

Maintain three maps:

• key -> value, key -> frequency.
• frequency -> ordered set of keys (LRU order within a frequency).

Also track minFreq, the smallest frequency present. Every access touches a key: remove it from its current frequency bucket, bump its frequency, add to the next bucket. If the emptied bucket was minFreq, increment minFreq.

Eviction: when full, remove the oldest key in the minFreq bucket (LFU, LRU tie-break). A new key starts at frequency 1, so minFreq resets to 1.

Worked example

Capacity 2, ops put(1,1) put(2,2) get(1) put(3,3) ... → 3 evicts 2 (freq 1, older) → returns [...,1,...,-1,3,...].

Complexity

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

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

class LFUCache {
    private int cap, minFreq;
    private Map<Integer, Integer> keyVal = new HashMap<>();
    private Map<Integer, Integer> keyFreq = new HashMap<>();
    private Map<Integer, LinkedHashSet<Integer>> freqKeys = new HashMap<>();

    public LFUCache(int capacity) {
        cap = capacity;
        minFreq = 0;
    }

    private void touch(int key) {
        int f = keyFreq.get(key);
        freqKeys.get(f).remove(key);
        if (freqKeys.get(f).isEmpty()) {
            freqKeys.remove(f);
            if (minFreq == f) minFreq++;
        }
        keyFreq.put(key, f + 1);
        freqKeys.computeIfAbsent(f + 1, z -> new LinkedHashSet<>()).add(key);
    }

    public int get(int key) {
        if (!keyVal.containsKey(key)) return -1;
        touch(key);
        return keyVal.get(key);
    }

    public void put(int key, int value) {
        if (cap <= 0) return;
        if (keyVal.containsKey(key)) {
            keyVal.put(key, value);
            touch(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, z -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
}