Topics › Stacks and Queues › Implementation Problems

LFU Cache

Hard TUF ID 960 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Design a cache with a fixed capacity that supports:

• get(key): return the value for key, or -1 if absent.
• put(key, value): update the value if the key is present; otherwise insert it. If inserting a new key would exceed the capacity, first evict the least frequently used key. If several keys share the lowest frequency, evict the least recently used among them.

Every key has a use counter. A new key starts at 1; every successful get and every put on an existing key adds 1. Both operations must run in O(1) average time.

Constraints: 1 ≤ capacity ≤ 10^4 on LeetCode (older versions allowed 0, which the Java file handles by storing nothing), keys and values are non-negative, at most 2 × 10^5 calls.

All implementations share one interface so the same tests can drive them:

interface Cache {
    int get(int key);
    void put(int key, int value);
}

Example

capacity = 2
put(1, 1)            freq: 1→1
put(2, 2)            freq: 1→1, 2→1
get(1) -> 1          freq: 1→2, 2→1
put(3, 3)            full; lowest freq is 1 (key 2): evict 2.  freq: 1→2, 3→1
get(2) -> -1
get(3) -> 3          freq: 1→2, 3→2
put(4, 4)            full; keys 1 and 3 both have freq 2, key 1 was used longer ago: evict 1
get(1) -> -1
get(3) -> 3
get(4) -> 4

What makes this harder than LRU. An LRU cache only needs one ordering, by recency. Here the eviction order is by the pair (frequency, last use time), and every operation changes the pair of the key it touches. The question is how to keep “the smallest pair” available in O(1).

Approach 1: Brute force, scan for the victim

Intuition. Store each entry as {key, value, freq, lastUsed}, where lastUsed comes from a counter tick that increases on every use, so a smaller tick means “used longer ago”. Lookups scan the list. On eviction, scan for the entry with the smallest freq, breaking ties by the smallest lastUsed.

Algorithm.

1. get: find the entry; if present, increment freq, set lastUsed = ++tick, return the value.
2. put on an existing key: update the value, freq and lastUsed.
3. put on a new key: if full, remove the entry with the smallest (freq, lastUsed); add {key, value, 1, ++tick}.

static class BruteLFU implements Cache {
    private final int capacity;
    private final List<int[]> entries = new ArrayList<>();   // {key, value, freq, lastUsed}
    private int tick = 0;

    BruteLFU(int capacity) { this.capacity = capacity; }

    private int find(int key) {
        for (int i = 0; i < entries.size(); i++) if (entries.get(i)[0] == key) return i;
        return -1;
    }

    public int get(int key) {
        int i = find(key);
        if (i == -1) return -1;
        int[] e = entries.get(i);
        e[2]++;
        e[3] = ++tick;
        return e[1];
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        int i = find(key);
        if (i != -1) {
            int[] e = entries.get(i);
            e[1] = value;
            e[2]++;
            e[3] = ++tick;
            return;
        }
        if (entries.size() == capacity) {
            int victim = 0;
            for (int j = 1; j < entries.size(); j++) {
                int[] a = entries.get(j), b = entries.get(victim);
                if (a[2] < b[2] || (a[2] == b[2] && a[3] < b[3])) victim = j;
            }
            entries.remove(victim);
        }
        entries.add(new int[]{key, value, 1, ++tick});
    }
}

Complexity. O(capacity) per operation for the scans. Space O(capacity).

Approach 2: Better, an ordered set keyed by (freq, lastUsed)

Intuition. The victim is the minimum of (freq, lastUsed). A balanced binary search tree keeps its elements sorted and gives the minimum in O(log n). Put every entry in a TreeSet ordered by that pair and keep a HashMap from key to entry for lookups.

There is one trap. A TreeSet locates an element by comparing it with the comparator. If we change freq or lastUsed while the entry is inside the set, the tree is no longer correctly ordered and remove may fail to find the entry. So every update is remove, modify, re-insert. Also, a TreeSet treats elements that compare as equal as duplicates; because every lastUsed value is unique, no two entries ever compare equal.

Algorithm.

1. touch(e): remove e from the set, increment freq, set lastUsed = ++tick, add e back.
2. get: look up the entry in the map; touch it; return the value.
3. put on a new key when full: pollFirst() gives the victim; remove it from the map too. Then insert the new entry in both structures.

static class TreeSetLFU implements Cache {
    private final int capacity;
    private final Map<Integer, int[]> map = new HashMap<>();       // key -> {key, value, freq, lastUsed}
    private final TreeSet<int[]> order = new TreeSet<>((a, b) ->
            a[2] != b[2] ? Integer.compare(a[2], b[2]) : Integer.compare(a[3], b[3]));
    private int tick = 0;

    TreeSetLFU(int capacity) { this.capacity = capacity; }

    private void touch(int[] e) {
        order.remove(e);                  // remove before changing the fields the comparator reads
        e[2]++;
        e[3] = ++tick;
        order.add(e);
    }

    public int get(int key) {
        int[] e = map.get(key);
        if (e == null) return -1;
        touch(e);
        return e[1];
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        int[] e = map.get(key);
        if (e != null) {
            e[1] = value;
            touch(e);
            return;
        }
        if (map.size() == capacity) {
            int[] victim = order.pollFirst();
            map.remove(victim[0]);
        }
        e = new int[]{key, value, 1, ++tick};
        map.put(key, e);
        order.add(e);
    }
}

Complexity. O(log capacity) per operation for the tree. Space O(capacity).

Approach 3: Optimal, one recency list per frequency

Intuition. Group the keys by frequency. Inside one frequency group, eviction is pure LRU, and we already know how to do LRU in O(1): a doubly linked list where the front is the most recent and the back is the least recent. So keep:

• nodes: key → node (each node stores key, value and freq);
• buckets: freq → doubly linked list of the nodes with exactly that frequency, most recent first;
• minFreq: the smallest frequency that currently has a non-empty list.

The victim is always the back of buckets.get(minFreq).

The only hard part is keeping minFreq correct in O(1), without searching. It can change in only two ways:

• Touching a node moves it from list f to list f + 1. If list f becomes empty and f was minFreq, the new minimum is f + 1, because the node we just moved is there. If list f is still non-empty, or f > minFreq, the minimum is unchanged.
• Inserting a new key puts it in list 1, so minFreq = 1. Nothing can be lower.

Eviction never needs to recompute minFreq: it is always followed immediately by inserting a new key, which resets minFreq to 1 anyway.

Algorithm.

1. touch(node): unlink it from buckets[freq]; if that list is now empty and minFreq == freq, increment minFreq; increment node.freq; add the node to the front of buckets[freq] (creating the list if needed).
2. get(key): if absent return -1; else touch and return the value.
3. put(key, value):
   • If present: update the value and touch.
   • Else: if full, remove the back of buckets[minFreq] and delete its key from nodes. Create the node with freq = 1, add it to buckets[1] and nodes, and set minFreq = 1.

static class LFUCache implements Cache {
    private static class Node {
        int key, value, freq = 1;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    /** Doubly linked list with sentinels; the front is the most recently used. */
    private static class DList {
        final Node head = new Node(0, 0), tail = new Node(0, 0);
        int size = 0;

        DList() { 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 unlink(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }

        Node removeLast() {
            Node node = tail.prev;
            unlink(node);
            return node;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> nodes = new HashMap<>();
    private final Map<Integer, DList> buckets = new HashMap<>();   // freq -> nodes used exactly freq times
    private int minFreq = 0;

    LFUCache(int capacity) { this.capacity = capacity; }

    private void touch(Node node) {
        DList list = buckets.get(node.freq);
        list.unlink(node);
        if (list.size == 0 && minFreq == node.freq) minFreq++;
        node.freq++;
        buckets.computeIfAbsent(node.freq, f -> new DList()).addFront(node);
    }

    public int get(int key) {
        Node node = nodes.get(key);
        if (node == null) return -1;
        touch(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        Node node = nodes.get(key);
        if (node != null) {
            node.value = value;
            touch(node);
            return;
        }
        if (nodes.size() == capacity) {
            Node victim = buckets.get(minFreq).removeLast();
            nodes.remove(victim.key);
        }
        node = new Node(key, value);
        nodes.put(key, node);
        buckets.computeIfAbsent(1, f -> new DList()).addFront(node);
        minFreq = 1;
    }
}

Dry run of the example (lists show keys, most recent first):

At get(3) list 1 empties while minFreq == 1, so minFreq moves to 2; that is exactly what makes the next eviction look in the right list.

Complexity. O(1) average per operation: a constant number of hash map accesses and pointer updates. Space O(capacity) for the nodes, plus at most one (possibly empty) list object per frequency value that has ever been reached.

Edge cases and pitfalls

• Capacity 0. put must store nothing, and get returns -1. Without the guard the optimal version would try to evict from a list that does not exist.
• put on an existing key is a use. It increases the frequency and refreshes recency. In the test put 1, put 2, put(1, 10), put 3, key 2 (frequency 1) is evicted and key 1 keeps the new value 10.
• Ties go to the least recent. With put 1, put 2, put 3 and capacity 2, key 1 is evicted; both had frequency 1, and 1 is older. Adding at the front and evicting from the back of each list gives this for free.
• Updating minFreq too eagerly. Increment it only when the emptied list was the minimum one. Emptying list 3 while minFreq is 1 must not change anything.
• Mutating TreeSet elements. In Approach 2, changing freq before removing the entry corrupts the set. Remove first, then modify, then add.
• Do not forget the hash map on eviction. Removing the node from its list but not from nodes makes a later get return an evicted value.

Related problems

• LRU Cache is the single-list version; each frequency bucket here is an LRU list.
• Implement Min Stack is another design problem that keeps a running minimum cheaply.
• Sliding Window Maximum also maintains an extreme value under updates, with a heap or a deque.
• Introduction to Doubly LL covers the pointer updates used by every bucket.