LFU Cache — O(1) Least Frequently Used Eviction

LFUCache(2)
put(1,1), put(2,2)
get(1)       → 1   (freq: {1:2, 2:1})
put(3,3)     → evicts key 2 (lowest freq)
get(2)       → -1  (evicted)

key_map:  {1: (val1, 2), 3: (val3, 1)}
freq_map: {1: OrderedDict({3: _}), 2: OrderedDict({1: _})}
min_freq: 1

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.min_freq = 0
        self.key_map = {}
        self.freq_map = defaultdict(OrderedDict)

    def _update(self, key):
        val, freq = self.key_map[key]
        del self.freq_map[freq][key]
        if not self.freq_map[freq] and freq == self.min_freq:
            self.min_freq += 1
        self.key_map[key] = (val, freq + 1)
        self.freq_map[freq + 1][key] = None

    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        self._update(key)
        return self.key_map[key][0]

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return
        if key in self.key_map:
            self._update(key)
            self.key_map[key] = (value, self.key_map[key][1])
            return
        if len(self.key_map) >= self.cap:
            evict_key, _ = self.freq_map[self.min_freq].popitem(last=False)
            del self.key_map[evict_key]
        self.key_map[key] = (value, 1)
        self.freq_map[1][key] = None
        self.min_freq = 1

class LFUCache {
    constructor(capacity) {
        this.cap = capacity;
        this.minFreq = 0;
        this.keyMap = new Map();
        this.freqMap = new Map();
    }
    _update(key) {
        const [val, freq] = this.keyMap.get(key);
        this.freqMap.get(freq).delete(key);
        if (this.freqMap.get(freq).size === 0 && freq === this.minFreq)
            this.minFreq++;
        this.keyMap.set(key, [val, freq + 1]);
        if (!this.freqMap.has(freq + 1)) this.freqMap.set(freq + 1, new Map());
        this.freqMap.get(freq + 1).set(key, null);
    }
    get(key) {
        if (!this.keyMap.has(key)) return -1;
        this._update(key);
        return this.keyMap.get(key)[0];
    }
    put(key, value) {
        if (this.cap === 0) return;
        if (this.keyMap.has(key)) {
            this._update(key);
            const [, freq] = this.keyMap.get(key);
            this.keyMap.set(key, [value, freq]);
            return;
        }
        if (this.keyMap.size >= this.cap) {
            const evict = this.freqMap.get(this.minFreq).keys().next().value;
            this.freqMap.get(this.minFreq).delete(evict);
            this.keyMap.delete(evict);
        }
        this.keyMap.set(key, [value, 1]);
        if (!this.freqMap.has(1)) this.freqMap.set(1, new Map());
        this.freqMap.get(1).set(key, null);
        this.minFreq = 1;
    }
}

import java.util.*;
class LFUCache {
    int cap, minFreq;
    Map<Integer, int[]> keyMap = new HashMap<>();
    Map<Integer, LinkedHashMap<Integer, Integer>> freqMap = new HashMap<>();
    public LFUCache(int capacity) { cap = capacity; }
    void update(int key) {
        int[] vf = keyMap.get(key);
        freqMap.get(vf[1]).remove(key);
        if (freqMap.get(vf[1]).isEmpty() && vf[1] == minFreq) minFreq++;
        vf[1]++;
        freqMap.computeIfAbsent(vf[1], k -> new LinkedHashMap<>()).put(key, vf[0]);
    }
    public int get(int key) {
        if (!keyMap.containsKey(key)) return -1;
        update(key); return keyMap.get(key)[0];
    }
    public void put(int key, int value) {
        if (cap == 0) return;
        if (keyMap.containsKey(key)) { update(key); keyMap.get(key)[0] = value; return; }
        if (keyMap.size() >= cap) {
            int evict = freqMap.get(minFreq).entrySet().iterator().next().getKey();
            freqMap.get(minFreq).remove(evict); keyMap.remove(evict);
        }
        keyMap.put(key, new int[]{value, 1});
        freqMap.computeIfAbsent(1, k -> new LinkedHashMap<>()).put(key, value);
        minFreq = 1;
    }
}

#include <unordered_map>
#include <map>
#include <list>
using namespace std;
class LFUCache {
    int cap, minFreq = 0;
    unordered_map<int, pair<int,int>> keyMap;
    unordered_map<int, list<int>> freqMap;
    unordered_map<int, list<int>::iterator> pos;
public:
    LFUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (!keyMap.count(key)) return -1;
        int f = keyMap[key].second;
        freqMap[f].erase(pos[key]);
        if (freqMap[f].empty() && f == minFreq) minFreq++;
        keyMap[key].second++;
        freqMap[f+1].push_front(key);
        pos[key] = freqMap[f+1].begin();
        return keyMap[key].first;
    }
    void put(int key, int value) {
        if (cap <= 0) return;
        if (keyMap.count(key)) { keyMap[key].first = value; get(key); return; }
        if ((int)keyMap.size() >= cap) {
            int evict = freqMap[minFreq].back();
            freqMap[minFreq].pop_back();
            keyMap.erase(evict); pos.erase(evict);
        }
        keyMap[key] = {value, 1};
        freqMap[1].push_front(key);
        pos[key] = freqMap[1].begin();
        minFreq = 1;
    }
};

/* C approach: fixed-size arrays with freq buckets and circular buffers */
/* Same conceptual flow: freq_bucket[f] = ring buffer of keys at frequency f */
/* min_freq tracks lowest occupied bucket */