LFU Cache

NeetCode: LFU Cache · LeetCode: 460. LFU Cache · Difficulty: Hard

Design a cache with a fixed capacity. get(key) returns the value or -1. put(key, value) inserts or updates the key. When the cache is full, evict the least frequently used key before inserting; if several keys share the lowest use count, evict the least recently used among them. Every get or put on a key counts as one use of it. Both operations must run in O(1) average time.

Example

Text

LFUCache(2)
put(1,1) put(2,2)
get(1)   -> 1
put(3,3)      evicts key 2 (use count 1 is lowest)
get(2)   -> -1
get(3)   -> 3
put(4,4)      keys 1 and 3 both have count 2; key 1 is older, so evict 1
get(1)   -> -1
get(3)   -> 3
get(4)   -> 4

Brute force: hash map plus a scan for the victim

Store {value, frequency, lastUsedTick} per key in a HashMap, with a global counter as the clock. get and updates are O(1). Eviction scans every entry and picks the smallest (frequency, lastUsedTick) pair, which applies both eviction rules at once. Every operation gets a new tick, so no two entries tie and the HashMap iteration order does not affect the victim.

Java

import java.util.HashMap;
import java.util.Map;

class LFUCache {
    private final int capacity;
    private long clock; // increases on every operation
    private final Map<Integer, long[]> entries = new HashMap<>(); // key -> {value, frequency, last used}

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

    public int get(int key) {
        clock++;
        long[] e = entries.get(key);
        if (e == null) {
            return -1;
        }
        e[1]++;        // one more use
        e[2] = clock;  // used just now
        return (int) e[0];
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        clock++;
        long[] e = entries.get(key);
        if (e != null) {
            e[0] = value;
            e[1]++;
            e[2] = clock;
            return;
        }
        if (entries.size() == capacity) {
            // O(capacity) scan: lowest frequency first, then oldest use.
            int victim = 0;
            long[] best = null;
            for (Map.Entry<Integer, long[]> en : entries.entrySet()) {
                long[] v = en.getValue();
                if (best == null || v[1] < best[1] || (v[1] == best[1] && v[2] < best[2])) {
                    best = v;
                    victim = en.getKey();
                }
            }
            entries.remove(victim);
        }
        entries.put(key, new long[]{value, 1, clock});
    }
}

public class Main {
    public static void main(String[] args) {
        LFUCache c = new LFUCache(2);
        c.put(1, 1);
        c.put(2, 2);
        System.out.println(c.get(1));
        c.put(3, 3);
        System.out.println(c.get(2));
        System.out.println(c.get(3));
        c.put(4, 4);
        System.out.println(c.get(1));
        System.out.println(c.get(3));
        System.out.println(c.get(4));

        LFUCache zero = new LFUCache(0);
        zero.put(1, 1);
        System.out.println("zero capacity: " + zero.get(1));
    }
}

Output

1
-1
3
-1
3
4
zero capacity: -1

Time: get is O(1); put is O(capacity) when it evicts. Space: O(capacity).

Optimal: key map, one list per frequency, and minFreq

Keys are grouped by use count. For each count f there is a doubly linked list of the keys used exactly f times, ordered from most recently used (front) to least recently used (back).

Text

freq 1:  front -> [4] -> [2] <- back
freq 3:  front -> [1] <- back            minFreq = 1

Touching a key (get, or put on an existing key) unlinks its node from the list for f and pushes it on the front of the list for f + 1.
Eviction removes the back node of the list for minFreq. That node has the lowest count and, among equals, is the least recently used.
Maintaining minFreq. After a touch, if the node came from the minFreq list and that list is now empty, the node's new list minFreq + 1 is the lowest, so minFreq increases by one. Inserting a new key sets minFreq = 1, because a new key has count 1.

The invariant: minFreq is always the smallest count that has a non-empty list, and each list is ordered by recency.

Storage. Linked structures in Java use null and mutable fields, so nodes are plain objects with prev and next references. Each FreqList has two sentinel nodes (head and tail), so linking and unlinking never need a case for the first or last node. The most recent node of a list is head.next and the least recent is tail.prev. nodeOf maps a key to its node, and lists maps a count to its FreqList; a list that becomes empty is removed from the map. The maps are only looked up by key and never iterated, so their unspecified iteration order does not matter. When the cache is full, the evicted node is reused for the new key, so at most capacity nodes exist.

Helpers:

FreqList.remove(node) unlinks a node from its list; FreqList.addFront(node) links it at the front.
touch(node) removes the node from the list for its count, increases the count, adds it to the next list, and updates minFreq.

Java

import java.util.HashMap;
import java.util.Map;

class LFUCache {
    private static class Node {
        int key;
        int value;
        int freq; // number of uses so far
        Node prev; // neighbour towards the front (more recent)
        Node next; // neighbour towards the back (less recent)
    }

    /** The doubly linked list for one frequency, with sentinel ends. */
    private static class FreqList {
        final Node head = new Node();
        final Node tail = new Node();

        FreqList() {
            head.next = tail;
            tail.prev = head;
        }

        boolean isEmpty() {
            return head.next == tail;
        }

        void addFront(Node n) {
            n.prev = head;
            n.next = head.next;
            head.next.prev = n;
            head.next = n;
        }

        void remove(Node n) {
            n.prev.next = n.next;
            n.next.prev = n.prev;
        }

        Node back() {
            return tail.prev;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> nodeOf = new HashMap<>();        // key -> node
    private final Map<Integer, FreqList> lists = new HashMap<>();     // frequency -> its list (only non-empty lists)
    private int minFreq;                                              // smallest frequency with a non-empty list

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

    /** Unlink a node from the list for its frequency; drop the list if it became empty. */
    private void detach(Node n) {
        FreqList list = lists.get(n.freq);
        list.remove(n);
        if (list.isEmpty()) {
            lists.remove(n.freq);
        }
    }

    private void attach(Node n) {
        lists.computeIfAbsent(n.freq, f -> new FreqList()).addFront(n);
    }

    /** Count one more use of a node. */
    private void touch(Node n) {
        detach(n);
        if (!lists.containsKey(minFreq)) {
            minFreq++; // the lowest list emptied, so this node becomes the lowest
        }
        n.freq++;
        attach(n);
    }

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

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node n = nodeOf.get(key);
        if (n != null) {
            n.value = value;
            touch(n);
            return;
        }
        if (nodeOf.size() == capacity) {
            // Evict the least recently used node of the lowest frequency, and reuse it.
            n = lists.get(minFreq).back();
            detach(n);
            nodeOf.remove(n.key);
        } else {
            n = new Node();
        }
        n.key = key;
        n.value = value;
        n.freq = 1;
        nodeOf.put(key, n);
        attach(n);
        minFreq = 1; // a new key has been used once
    }
}

public class Main {
    public static void main(String[] args) {
        LFUCache c = new LFUCache(2);
        c.put(1, 1);
        c.put(2, 2);
        System.out.println(c.get(1));
        c.put(3, 3);
        System.out.println(c.get(2));
        System.out.println(c.get(3));
        c.put(4, 4);
        System.out.println(c.get(1));
        System.out.println(c.get(3));
        System.out.println(c.get(4));

        LFUCache zero = new LFUCache(0);
        zero.put(1, 1);
        System.out.println("zero capacity: " + zero.get(1));
    }
}

Output

1
-1
3
-1
3
4
zero capacity: -1

Trace of the example with capacity = 2:

Operation	freq 1 list	freq 2 list	minFreq
`put(1)`, `put(2)`	2, 1		1
`get(1)`	2	1	1
`put(3)` evicts 2	3	1	1
`get(3)`		3, 1	2
`put(4)` evicts back of freq 2 (key 1)	4	3	1

Time: get and put are O(1) average (a few hash lookups and constant reference updates). Space: O(capacity).

Edge cases

capacity = 0: put does nothing and get returns -1.
put on an existing key updates the value and counts as a use.
Ties on frequency are broken by recency, which the order inside each list provides.

How to explain it in an interview

Evicting by frequency and then by recency needs the keys grouped by use count, each group ordered by recency.
Keep one doubly linked list per frequency, and a map from key to its node.
A use moves the node from the list for f to the front of the list for f + 1, in O(1).
Keep minFreq. The victim is the back of the minFreq list.
minFreq rises by one when a touch empties the minFreq list, and resets to 1 when a new key is inserted.
Java nodes are objects linked by references; an evicted node is reused for the new key.
All operations are O(1) average; space is O(capacity).