LFU Cache

July 2026 · 21 min read

If the LRU cache was a hash map married to a doubly linked list, the LFU cache is a hash map married to a list of doubly linked lists. It is one of the hardest "keep everything O(1)" designs asked in interviews, because it juggles two orderings at once. Get the invariant right and both operations are constant time; miss it and you are scanning for a minimum on every eviction. This is LeetCode 460.

Why LFU Is Genuinely Harder Than LRU

LRU has a single ordering: recency. The least-recently-used item sits at one end of one list, and eviction is "remove the back." LFU adds a second, dominant ordering: frequency. You must evict the least-frequently-used key — and when several keys are tied on frequency, break the tie by evicting the least-recently-used among them. So you are maintaining a primary sort by use-count and a secondary sort by recency, and both get and put still have to run in O(1).

The naive design — store a frequency counter per key and scan for the minimum at eviction — is O(n) per eviction. The whole art is removing that scan.

It is worth pausing on how costly that scan really is. Eviction is not a rare event — under memory pressure it fires on nearly every insertion, so an O(n) minimum-search there is not an occasional tax but the dominant cost of a hot, full cache. Everything below exists to replace that linear search with a single integer read of min_freq, turning the worst-case operation into an O(1) one.

The Frequency-Bucket Design

Bucket keys by their current frequency, and make each bucket an LRU list. Three pieces:

• keyNode: unordered_map<int, list<Node>::iterator> — key to its node, for O(1) lookup.
• freqList: unordered_map<int, list<Node>> — frequency to the list of keys currently at that frequency. Each list is recency-ordered: front = most-recently-used, back = least.
• minFreq: the smallest frequency any key currently has — a single integer that points at the bucket to evict from.

On every access (a get, or a put that updates an existing key) the key's frequency rises by one, so its node moves from bucket f to bucket f+1. Because both buckets are std::lists, that move is an O(1) splice — no allocation, no copy, and the stored iterator stays valid. Push it to the front of the new bucket so recency ordering is preserved.

The Invariant That Makes It O(1)

Everything hinges on one claim about minFreq:

Here is why. Consider a promotion of a node at frequency f; it moves to f+1. The global minimum frequency can only change if f == minFreq and that node was the last one in bucket f. In that case bucket f is now empty, and — crucially — every remaining key had frequency ≥ f before (since f was the minimum) and none has frequency f any more, so every key now has frequency ≥ f+1. Therefore the new minimum is exactly f+1. If bucket f is not empty after the promotion, some key still sits at minFreq, so it does not change. And any freshly inserted key has frequency 1, which is the smallest possible, so insertion forces minFreq = 1.

Because the minimum can only creep up by one or snap back to one, you never scan the buckets to find it — you just maintain the integer. That single fact is what turns eviction from O(n) into O(1).

Eviction: Least-Recently-Used Among the Least-Frequently-Used

When the cache is full and a new key arrives, evict from bucket freqList[minFreq] — those are the least-frequently-used keys by definition. Among them, take the back of the list: since every access pushes to the front, the back is the least-recently-used. One line, O(1), and it satisfies both the primary (frequency) and the tie-break (recency) rule simultaneously.

The Implementation

Using std::list and splice, the whole thing is compact. The promotion helper is the heart of it:

class LFUCache {
    struct Node { int key, val, freq; };
    int cap, minFreq;
    std::unordered_map<int, std::list<Node>::iterator> keyNode;   // key -> node
    std::unordered_map<int, std::list<Node>>            freqList;   // freq -> LRU list

    void touch(std::list<Node>::iterator it) {
        int f = it->freq++;                              // old freq f; node is now f+1
        // O(1) move; splice preserves `it`, so keyNode needs no update
        freqList[f + 1].splice(freqList[f + 1].begin(), freqList[f], it);
        if (freqList[f].empty()) {
            freqList.erase(f);
            if (minFreq == f) ++minFreq;                // the ONLY increment of minFreq
        }
    }

public:
    LFUCache(int capacity) : cap(capacity), minFreq(0) {}

    int get(int key) {
        auto it = keyNode.find(key);
        if (it == keyNode.end()) return -1;             // miss -> -1
        touch(it->second);
        return it->second->val;
    }

    void put(int key, int value) {
        if (cap <= 0) return;
        auto it = keyNode.find(key);
        if (it != keyNode.end()) {                      // update existing: also a use
            it->second->val = value;
            touch(it->second);
            return;
        }
        if ((int)keyNode.size() == cap) {               // evict before inserting
            auto& lst = freqList[minFreq];
            keyNode.erase(lst.back().key);              // LRU among LFU = back of min bucket
            lst.pop_back();
            if (lst.empty()) freqList.erase(minFreq);
        }
        freqList[1].push_front({key, value, 1});
        keyNode[key] = freqList[1].begin();
        minFreq = 1;                                    // new key -> min resets to 1
    }
};

The elegance is that splice moves a node between two different lists in O(1) and keeps the iterator valid, so keyNode never has to be rewired on a promotion — the same reason iterator stability made the std::list LRU work. A from-scratch version replaces each std::list with a hand-rolled doubly linked list of sentinels (as in the LRU post) and stores raw Node* in keyNode; the logic is identical, you just write the four pointer assignments yourself:

struct Node {
    int key, val, freq;
    Node *prev, *next;
};

// One sentinel-terminated LRU list per frequency. head->next is the most
// recently used; tail->prev is the eviction candidate.
struct Bucket {
    Node *head, *tail;
    int   size;

    Bucket() : head(new Node{}), tail(new Node{}), size(0) {
        head->next = tail; tail->prev = head;
    }

    void push_front(Node* n) {
        n->next = head->next; n->prev = head;
        head->next->prev = n; head->next = n;
        ++size;
    }

    void erase(Node* n) {                 // O(1): we already hold the node
        n->prev->next = n->next;
        n->next->prev = n->prev;
        --size;
    }

    Node* back() const { return tail->prev; }
    bool  empty() const { return size == 0; }
};

// Promotion is now erase-from-f, push-to-(f+1) — the manual splice.
void touch(Node* n) {
    int f = n->freq++;
    bucket[f].erase(n);
    bucket[f + 1].push_front(n);
    if (bucket[f].empty() && minFreq == f) ++minFreq;
}

Written out this way the reason a doubly linked list is mandatory becomes concrete: erase(n) needs n->prev, and without it the promotion would cost a O(bucket size) scan — which would destroy the O(1) guarantee on every single access, not just on eviction.

Complexity: get and put are both O(1) (one hash lookup, one splice, an integer update), and memory is O(capacity) — one node and one map entry per key, plus one small bucket list per distinct frequency in use.

Dry Run: Capacity 2

Trace put(1,1) put(2,2) get(1) put(3,3) get(2) get(3) put(4,4) get(1) get(3) get(4). Columns show each live key with its frequency:

Two evictions show both rules in action. At put(3,3) the live keys are 1 (freq 2, just promoted by get(1)) and 2 (freq 1); min_freq is 1, so the victim comes from bucket 1 — key 2 — even though key 1 was touched less recently. Frequency dominates recency. At put(4,4) the live keys are 1 and 3, now both at freq 2 with min_freq = 2; the tie is broken by recency, and since get(3) had just promoted key 3 to the front of bucket 2, key 1 is the least-recently-used of the pair and is evicted. When frequencies tie, recency decides — exactly the back of freqList[min_freq].

LRU vs. LFU in Practice

LFU's Achilles heel is one-hit-wonder pollution: a key that was briefly hammered — a viral link, a one-off batch job — accrues a huge frequency count and then refuses to leave, squatting in the cache long after it stopped being useful, because nothing ever lowers its count. The fix is aging: periodically decay all counts (halve them, or subtract a global epoch), so popularity has to be renewed to be retained.

Modern production caches do not pick a side. TinyLFU and its refinement W-TinyLFU — the policy behind Java's Caffeine library — keep an approximate, aging frequency sketch (a count-min sketch) to decide admissions, fronted by a small recency-based window cache. The result blends LRU's responsiveness to bursts with LFU's respect for long-run popularity, at a fraction of the bookkeeping cost of exact LFU. As with LRU, the exact algorithm is the thing you implement in an interview; the approximation is the thing that ships.

Check Yourself

Six situations. Pick the statement that is actually true.

Practice

• LeetCode 460 — LFU Cache core get both operations to O(1); verify the min_freq invariant by assertion.
• LeetCode 146 — LRU Cache prereq the single-ordering warm-up this builds on.
• LeetCode 432 — All O`one Data Structure buckets the same "buckets of equal counts in a linked list" idea, incrementing and decrementing.
• LeetCode 2349 — Design a Number Container System multimap keep a per-value ordered set in sync with a key map.
• LeetCode 895 — Maximum Frequency Stack freq frequency buckets again, popping the most-frequent-then-most-recent.
• LeetCode 588 — Design In-Memory File System design more composite-structure design practice.