Blind Plus 100 Visualized

#99 · Design

LFU Cache

Design a Least Frequently Used cache with get(key) and put(key, value) in O(1) average time. When full, evict the key used the fewest times; if several tie, evict the least recently used among them.

HardLeetCode
  • Current node
  • Link just rewired
  • Done / in result
  • Marked
  • Rejected
  • Dummy head
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Hash maps: key → value and key → frequency

Constant-time lookup of a key's value and of how many times it has been used. A hit increments the key's frequency, a miss touches nothing.

Memory layout

Two hash tables with at most capacity entries (or one table of nodes that store both).

OperationCost
lookup / updateO(1) average

Frequency buckets in recency order

For every frequency f, a list of the keys currently used f times, ordered by recency. Moving a key from bucket f to bucket f + 1 is an O(1) removal plus an O(1) insertion at the front; the victim is the LAST key of the lowest non-empty bucket.

Memory layout

A map from frequency to an ordered collection (ordered set, or a doubly linked list per frequency).

OperationCost
move between bucketsO(1) with linked lists or ordered sets

minFreq counter

The smallest frequency that still has a key. After a bump it increases by one only when the bump emptied the minimum bucket; a new key resets it to 1. This avoids scanning for the lowest frequency.

Memory layout

One integer.

OperationCost
updateO(1)

Why it fits

  • LFU has two orderings at once (by frequency, then by recency), which the bucket-of-lists structure represents explicitly: rows by frequency, order inside a row by recency.
  • Because frequencies only ever increase by one, a key moves to the NEXT bucket and minFreq changes in a trivially predictable way, which makes O(1) possible.
  • Using a removable-in-O(1) list per bucket (not an array) is what keeps the bump O(1) instead of O(bucket size).

Why alternatives degrade

Min-heap keyed by (frequency, time):
Every use needs a heap update: O(log n), and a heap cannot delete an arbitrary key without extra indexing.
Array scan for the victim:
Eviction costs O(n).
Sorted map by (frequency, time):
Each bump is a delete plus insert in a balanced tree: O(log n).

Four approaches, from naive to production

1 · beginner

Array of entries, scan for the victim

time O(n) per operationspace O(capacity)

Keep each entry with its use count and last-use time. get and put find the key by scanning; eviction scans for the smallest count (oldest use on ties).

class LFUCache {
    struct Entry { int key, value, freq; long long used; };
    vector<Entry> entries;
    long long clock = 0;
    int capacity;
public:
    LFUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        Entry* e = nullptr; for (auto& x : entries) if (x.key == key) { e = &x; break; }
        if (!e) return -1;
        e->freq++;
        e->used = ++clock;
        return e->value;
    }
    void put(int key, int value) {
        if (capacity <= 0) return;
        Entry* e = nullptr; for (auto& x : entries) if (x.key == key) { e = &x; break; }
        if (e) {
            e->value = value;
            e->freq++;
            e->used = ++clock;
            return;
        }
        if ((int)entries.size() == capacity) {
            int victim = 0;
            for (int i = 1; i < (int)entries.size(); i++) {
                const Entry& a = entries[i]; const Entry& b = entries[victim];
                if (a.freq < b.freq || (a.freq == b.freq && a.used < b.used)) victim = i;
            }
            entries.erase(entries.begin() + victim);
        }
        entries.push_back({key, value, 1, ++clock});
    }
};

Flaws & bottlenecks

  • Every operation scans the whole array.
  • A logical clock must be kept for tie-breaking.
  • Too slow at 10⁵ capacity.

Interviewer cross-questions

Why do you need the last-use time?

Say: LFU only says "fewest uses"; ties must be broken by recency, and the timestamp provides it.

Does put on an existing key count as a use?

Say: Yes, here and in the problem statement: it increments the frequency.

How do you avoid the scan?

Say: Group keys by frequency in recency order and remember the minimum frequency.

2 · intermediate

Frequency buckets as arrays

time O(bucket size) per bumpspace O(capacity)

Maps give value and frequency per key; buckets[f] is an array of keys, most recent first; minFreq names the lowest non-empty bucket. A bump removes the key from its bucket and unshifts it into the next one.

class LFUCache {
    unordered_map<int, int> values;
    unordered_map<int, int> freqOf;
    unordered_map<int, list<int>> buckets; // front = most recently used
    int minFreq = 0;
    int capacity;
    void bump(int key) {
        int f = freqOf[key];
        list<int>& bucket = buckets[f];
        bucket.remove(key);
        if (bucket.empty()) {
            buckets.erase(f);
            if (minFreq == f) minFreq = f + 1;
        }
        freqOf[key] = f + 1;
        buckets[f + 1].push_front(key);
    }
public:
    LFUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        if (!values.count(key)) return -1;
        bump(key);
        return values[key];
    }
    void put(int key, int value) {
        if (capacity <= 0) return;
        if (values.count(key)) {
            values[key] = value;
            bump(key);
            return;
        }
        if ((int)values.size() == capacity) {
            list<int>& bucket = buckets[minFreq];
            int victim = bucket.back(); bucket.pop_back();
            if (bucket.empty()) buckets.erase(minFreq);
            values.erase(victim);
            freqOf.erase(victim);
        }
        values[key] = value;
        freqOf[key] = 1;
        buckets[1].push_front(key);
        minFreq = 1;
    }
};

Flaws & bottlenecks

  • splice(indexOf) and unshift are O(bucket size).
  • Many keys at the same frequency make bumps slow.
  • Several structures to keep consistent (three maps and minFreq).

Interviewer cross-questions

When does minFreq change?

Say: It increases by 1 when a bump empties bucket minFreq (the key just moved to minFreq + 1); a new key sets it to 1.

Why take the victim from the end of the bucket?

Say: The bucket is ordered most recent first, so the last key is the least recently used among keys with the lowest frequency.

How do you make a bump O(1)?

Say: Use an ordered set or a doubly linked list per bucket so removal does not shift elements.

3 · advanced

Frequency buckets as ordered sets: O(1)

time O(1) per operationspace O(capacity)

Same as before, but each bucket is an insertion-ordered set (a hash set that remembers insertion order). Removing a key and adding it back is O(1), and the victim is the first (oldest) element of bucket minFreq.

class LFUCache {
    unordered_map<int, int> values;
    unordered_map<int, int> freqOf;
    unordered_map<int, list<int>> buckets; // front = oldest, back = newest
    unordered_map<int, list<int>::iterator> where;
    int minFreq = 0;
    int capacity;
    void bump(int key) {
        int f = freqOf[key];
        list<int>& bucket = buckets[f];
        bucket.erase(where[key]);
        if (bucket.empty()) {
            buckets.erase(f);
            if (minFreq == f) minFreq = f + 1;
        }
        freqOf[key] = f + 1;
        list<int>& next = buckets[f + 1];
        next.push_back(key); where[key] = prev(next.end());
    }
public:
    LFUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        if (!values.count(key)) return -1;
        bump(key);
        return values[key];
    }
    void put(int key, int value) {
        if (capacity <= 0) return;
        if (values.count(key)) {
            values[key] = value;
            bump(key);
            return;
        }
        if ((int)values.size() == capacity) {
            list<int>& bucket = buckets[minFreq];
            int victim = bucket.front();
            bucket.pop_front();
            if (bucket.empty()) buckets.erase(minFreq);
            values.erase(victim);
            freqOf.erase(victim); where.erase(victim);
        }
        values[key] = value;
        freqOf[key] = 1;
        list<int>& first = buckets[1];
        first.push_back(key); where[key] = prev(first.end());
        minFreq = 1;
    }
};

Flaws & bottlenecks

  • Relies on the language providing an insertion-ordered set (JavaScript Set, Java LinkedHashSet, Python dict keys, C++ list + iterator map).
  • The order of the "oldest" element differs between libraries; reading it needs care.
  • Still three maps plus minFreq to keep in sync.

Interviewer cross-questions

Why is an ordered set enough?

Say: It supports O(1) delete of an arbitrary key and O(1) append, and iteration yields keys oldest first, which gives the LRU victim.

What if the language has no ordered set?

Say: Build the bucket as a doubly linked list plus a map from key to node, exactly as in LRU Cache.

What is the worst-case cost of put?

Say: O(1) average: a constant number of hash operations; no loop over entries.

4 · expert

Explicit doubly linked frequency lists

time O(1) per operationspace O(capacity)

Each node stores key, value and frequency and sits in the FreqList (doubly linked, with dummy ends) of its frequency. A map gives key → node; another gives frequency → list. Bumping unlinks the node and pushes it onto the next list; eviction removes the last node of list minFreq.

struct Node {
    int key, value, freq; Node *prev, *next;
    Node(int k, int v, int f = 1) : key(k), value(v), freq(f), prev(nullptr), next(nullptr) {}
};
struct FreqList {
    Node* head = new Node(0, 0, 0);
    Node* tail = new Node(0, 0, 0);
    int size = 0;
    FreqList() { head->next = tail; tail->prev = head; }
    void addFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
        size++;
    }
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        size--;
    }
    Node* removeLast() {
        Node* node = tail->prev;
        remove(node);
        return node;
    }
};
class LFUCache {
    unordered_map<int, Node*> nodes;
    unordered_map<int, FreqList*> lists;
    int minFreq = 0;
    int capacity;
    void bump(Node* node) {
        FreqList* list = lists[node->freq];
        list->remove(node);
        if (list->size == 0) {
            lists.erase(node->freq); delete list;
            if (minFreq == node->freq) minFreq++;
        }
        node->freq++;
        FreqList*& next = lists[node->freq];
        if (!next) next = new FreqList();
        next->addFront(node);
    }
public:
    LFUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        auto it = nodes.find(key);
        Node* node = it == nodes.end() ? nullptr : it->second;
        if (!node) return -1;
        bump(node);
        return node->value;
    }
    void put(int key, int value) {
        if (capacity <= 0) return;
        auto it = nodes.find(key);
        Node* existing = it == nodes.end() ? nullptr : it->second;
        if (existing) {
            existing->value = value;
            bump(existing);
            return;
        }
        if ((int)nodes.size() == capacity) {
            FreqList* list = lists[minFreq];
            Node* victim = list->removeLast();
            if (list->size == 0) { lists.erase(minFreq); delete list; }
            nodes.erase(victim->key);
            delete victim;
        }
        Node* node = new Node(key, value);
        nodes[key] = node;
        FreqList*& first = lists[1];
        if (!first) first = new FreqList();
        first->addFront(node);
        minFreq = 1;
    }
};

Flaws & bottlenecks

  • Many small objects: allocation and GC pressure (array-backed slots would avoid it).
  • More code and more places for pointer mistakes.
  • Empty lists must be deleted and minFreq maintained, or stale buckets accumulate.

Interviewer cross-questions

Why store the frequency in the node?

Say: The bump then needs no extra lookup: the node tells which list it is in, and the freq → list map finds that list.

What are the edge cases?

Say: Capacity 0 (nothing is stored), updating an existing key (counts as a use, no eviction), evicting from a bucket that becomes empty, and bumping the only key in the minimum bucket (minFreq must advance).

How would you make it thread safe?

Say: Use one lock around every operation (get also mutates), or shard the cache by key hash with a lock per shard; global LFU ordering across shards needs coordination.

Synchronized code walkthrough

Showing: Array of entries, scan for the victim — shares the player above; click any step to jump.

class LFUCache {
    struct Entry { int key, value, freq; long long used; };
    vector<Entry> entries;
    long long clock = 0;
    int capacity;
public:
    LFUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        Entry* e = nullptr; for (auto& x : entries) if (x.key == key) { e = &x; break; }
        if (!e) return -1;
        e->freq++;
        e->used = ++clock;
        return e->value;
    }
    void put(int key, int value) {
        if (capacity <= 0) return;
        Entry* e = nullptr; for (auto& x : entries) if (x.key == key) { e = &x; break; }
        if (e) {
            e->value = value;
            e->freq++;
            e->used = ++clock;
            return;
        }
        if ((int)entries.size() == capacity) {
            int victim = 0;
            for (int i = 1; i < (int)entries.size(); i++) {
                const Entry& a = entries[i]; const Entry& b = entries[victim];
                if (a.freq < b.freq || (a.freq == b.freq && a.used < b.used)) victim = i;
            }
            entries.erase(entries.begin() + victim);
        }
        entries.push_back({key, value, 1, ++clock});
    }
};