Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

LFU Cache
DSA

LFU Cache

Understand how to design a Least Frequently Used cache with efficient access and eviction operations.

An LFU cache evicts the least frequently used entry; ties break by recency.

The upgrade from LRU:

Group keys into buckets per frequency. Each bucket keeps its keys in recency order (a linked hash set), so both “bump frequency” and “evict coldest” are O(1).

Focus on recognizing:

“Least frequently used” + tie-break by recency = freq buckets + ordered sets

Core Template

The eviction decision that separates LFU from LRU — a touch count saves a key’s life:

LFU Cache

Evict the least-frequently-used item; ties broken by least-recently-used.

Track frequency per key. On get, bump frequency (promote to a higher tier). On put when full, evict the key in the lowest-frequency tier (and among those, least recently used). Implemented with frequency buckets + recency lists for O(1) operations.

FREQ BUCKETS VISUALIZER
Steps –
▶ freq 1
∅
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        get(key): freq[key]++  (promote tier)
                      
                        2
                        put(key, val):
                      
                        3
                          if full and key is NEW:
                      
                        4
                            evict min-frequency key (LRU tie-break)
                      
                        5
                          store val; freq[key]++ or = 1
                      
class LFUCache {
    private final int cap;
    private int minFreq = 0;
    private final Map<Integer, Integer> vals = new HashMap<>();
    private final Map<Integer, Integer> freqs = new HashMap<>();
    private final Map<Integer, LinkedHashSet<Integer>> buckets =
            new HashMap<>();   // freq → keys, oldest first

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

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

    public void put(int key, int value) {
        if (cap == 0) return;

        if (vals.containsKey(key)) {
            vals.put(key, value);
            bump(key);
            return;
        }

        if (vals.size() == cap) evict();

        vals.put(key, value);
        freqs.put(key, 1);
        bucket(1).add(key);
        minFreq = 1;
    }

    private LinkedHashSet<Integer> bucket(int f) {
        return buckets.computeIfAbsent(f, k -> new LinkedHashSet<>());
    }

    private void bump(int key) {
        int f = freqs.get(key);
        bucket(f).remove(key);
        if (bucket(f).isEmpty()) {
            buckets.remove(f);
            if (minFreq == f) minFreq++;
        }
        freqs.put(key, f + 1);
        bucket(f + 1).add(key);
    }

    private void evict() {
        int victim = buckets.get(minFreq).iterator().next(); // oldest
        buckets.get(minFreq).remove(victim);
        if (buckets.get(minFreq).isEmpty()) buckets.remove(minFreq);
        vals.remove(victim);
        freqs.remove(victim);
    }
}
from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.min_freq = 0
        self.vals = {}
        self.freqs = {}
        self.buckets = defaultdict(OrderedDict)  # freq -> {key: None}

    def get(self, key: int) -> int:
        if key not in self.vals:
            return -1
        self._bump(key)
        return self.vals[key]

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return

        if key in self.vals:
            self.vals[key] = value
            self._bump(key)
            return

        if len(self.vals) == self.cap:
            victim, _ = self.buckets[self.min_freq].popitem(last=False)
            del self.freqs[victim]
            del self.vals[victim]

        self.vals[key] = value
        self.freqs[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1

    def _bump(self, key):
        f = self.freqs[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq += 1
        self.freqs[key] = f + 1
        self.buckets[f + 1][key] = None
class LFUCache {
    int cap;
    int minFreq = 0;
    unordered_map<int, pair<int, int>> kv;      // key -> {value, freq}
    unordered_map<int, list<int>> buckets;      // freq -> keys, newest front
    unordered_map<int, list<int>::iterator> pos;

public:
    LFUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = kv.find(key);
        if (it == kv.end()) return -1;
        touch(it);
        return it->second.first;
    }

    void put(int key, int value) {
        if (cap <= 0) return;

        auto it = kv.find(key);
        if (it != kv.end()) {
            it->second.first = value;
            touch(it);
            return;
        }

        if ((int)kv.size() == cap) {
            int victim = buckets[minFreq].back();
            buckets[minFreq].pop_back();
            pos.erase(victim);
            kv.erase(victim);
        }

        minFreq = 1;
        kv[key] = {value, 1};
        buckets[1].push_front(key);
        pos[key] = buckets[1].begin();
    }

private:
    void touch(unordered_map<int, pair<int, int>>::iterator it) {
        int key = it->first;
        int f = it->second.second++;

        buckets[f].erase(pos[key]);
        if (buckets[f].empty()) {
            buckets.erase(f);
            if (minFreq == f) minFreq++;
        }
        buckets[f + 1].push_front(key);
        pos[key] = buckets[f + 1].begin();
    }
};
class LFUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.minFreq = 0;
    this.kv = new Map();      // key -> { value, freq }
    this.buckets = new Map(); // freq -> Set(keys), oldest first
  }

  get(key) {
    if (!this.kv.has(key)) return -1;
    this.#touch(key);
    return this.kv.get(key).value;
  }

  put(key, value) {
    if (this.cap <= 0) return;

    if (this.kv.has(key)) {
      this.kv.get(key).value = value;
      this.#touch(key);
      return;
    }

    if (this.kv.size === this.cap) {
      const victim = this.buckets.get(this.minFreq).keys().next().value;
      this.buckets.get(this.minFreq).delete(victim);
      this.kv.delete(victim);
    }

    this.kv.set(key, { value, freq: 1 });
    this.minFreq = 1;
    this.#bucket(1).add(key);
  }

  #bucket(f) {
    if (!this.buckets.has(f)) this.buckets.set(f, new Set());
    return this.buckets.get(f);
  }

  #touch(key) {
    const entry = this.kv.get(key);
    this.buckets.get(entry.freq).delete(key);
    if (this.buckets.get(entry.freq).size === 0) {
      this.buckets.delete(entry.freq);
      if (this.minFreq === entry.freq) this.minFreq++;
    }
    entry.freq++;
    this.#bucket(entry.freq).add(key);
  }
}

Same skeleton everywhere: vals + freqs + buckets, with minFreq maintained incrementally.

What Changed from LRU?

Buckets replace one recency list

LRU orders everything in a single list. LFU needs frequency first, recency second — so each frequency gets its own ordered set.

minFreq moves incrementally

New keys enter at freq 1 (minFreq = 1). When a bucket empties, minFreq++. Never scan for the minimum — that would be O(n).

LFU = LRU’s map discipline + one ordered set per frequency level.

Common Mistakes

Scanning for the least-frequent key on eviction.

Track minFreq as you go — it only ever moves up by one or resets to 1 on insert.

Forgetting the recency tie-break.

Within a bucket, evict the oldest key — that’s why buckets are insertion-ordered structures, not plain sets (Java LinkedHashSet, Python OrderedDict, C++ list, JS Set).

Zero-capacity guard.

put on a capacity-0 cache must no-op before any eviction logic runs.

Complexity

OperationTime
getO(1)
putO(1)
SpaceO(capacity)

My Private Notes

Notes are auto-saved locally to this device.