Problem statement

Design a cache that evicts the least frequently used key when it is full. Every key has a use counter: it starts at 1 when the key is inserted and goes up by one each time the key is read with get or updated with put.

Write the class LFUCache:

• LFUCache(int capacity) creates an empty cache that holds at most capacity keys.
• int get(int key) returns the value of key if it is in the cache, otherwise -1.
• void put(int key, int value) sets the value of key if it is present; otherwise inserts it. If inserting would exceed capacity, first remove the key with the smallest use counter; if several keys tie, remove the one that was used least recently (read or written longest ago).

Both get and put must run in O(1) average time.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["LFUCache","put","put","get","get","put","get","get","put","get","get","get"]
[[2],[5,50],[6,60],[5],[5],[7,70],[6],[7],[8,80],[7],[5],[8]]
Output: [null,null,null,50,50,null,-1,70,null,-1,50,80]
Explanation: After two reads key 5 has counter 3 and key 6 counter 1, so inserting 7 evicts 6. Key 7 is read once (counter 2); inserting 8 then evicts 7, the less frequently used of 5 and 7.

Example 2

Input: ["LFUCache","put","get","put","get","get","put","get"]
[[1],[2,1],[2],[3,2],[2],[3],[3,0],[3]]
Output: [null,null,1,null,-1,2,null,0]
Explanation: With room for one key, inserting 3 evicts 2. Updating 3 to 0 keeps it (0 is a real value).

Constraints

• 1 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9
• At most 2 * 10^5 calls are made to get and put

Hints for LFU Cache

1. Hint 1

   You need the key with the smallest counter, and among those the least recently used — an LRU order inside each counter value.

2. Hint 2

   Group the keys by counter: for every counter f, a doubly linked list (or an insertion-ordered set) of the keys with that counter, oldest use first.

3. Hint 3

   Track minFreq, the smallest counter present. A use moves a key from list f to the end of list f + 1 (and bumps minFreq if list f emptied and was the minimum). A brand-new key always resets minFreq to 1. Eviction takes the front of list minFreq.

How to solve LFU Cache

Keep a hash map from key to its node (value and counter) and, for every counter value, a doubly linked list of the keys with that counter in order of last use. Together with the smallest counter in use, minFreq, every operation touches a constant number of nodes.

Approach

1. touch(key): unlink its node from list freq; if that list is now empty and freq == minFreq, increase minFreq. Increase the node's counter and append it to the end of the list for the new counter.
2. get(key): if absent return -1; otherwise touch it and return its value.
3. put(key, value) on a present key: set the value and touch it.
4. put on a new key: if the cache is full, remove the node at the front of list minFreq (least recently used among the least frequently used) and drop it from the map. Insert the new node with counter 1 at the end of list 1 and set minFreq = 1.

Why it works

Within one list, nodes are appended when they arrive at that counter, so the front is the one used longest ago; across lists, minFreq names the smallest counter in use. It only changes in two ways: a use can empty the minimum list, and then the moved key sits at minFreq + 1, the new minimum; a new key has counter 1, the smallest possible. So the front of list minFreq is always exactly the key the rules evict.

Complexity

• Time — O(1) average per get and put
• Space — O(capacity)

Pitfalls

• Updating an existing key with put counts as a use: its counter goes up.
• Evict before inserting the new key — otherwise the new key (counter 1) could be evicted immediately.
• Reset minFreq to 1 after inserting a new key, not to whatever it was.

Reference solution

Python

from collections import defaultdict, OrderedDict

class LFUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.node = {}                          # key -> [value, counter]
        self.byFreq = defaultdict(OrderedDict)  # counter -> keys, least recently used first
        self.minFreq = 0

    def _touch(self, key):
        f = self.node[key][1]
        del self.byFreq[f][key]
        if not self.byFreq[f]:
            del self.byFreq[f]
            if self.minFreq == f:
                self.minFreq = f + 1
        self.node[key][1] = f + 1
        self.byFreq[f + 1][key] = None

    def get(self, key: int) -> int:
        if key not in self.node:
            return -1
        self._touch(key)
        return self.node[key][0]

    def put(self, key: int, value: int) -> None:
        if key in self.node:
            self.node[key][0] = value
            self._touch(key)
            return
        if len(self.node) == self.cap:
            old, _ = self.byFreq[self.minFreq].popitem(last=False)
            if not self.byFreq[self.minFreq]:
                del self.byFreq[self.minFreq]
            del self.node[old]
        self.node[key] = [value, 1]
        self.byFreq[1][key] = None
        self.minFreq = 1

Java

class LFUCache {
    private int cap, minFreq = 0;
    private HashMap<Integer, int[]> node = new HashMap<>(); // key -> {value, counter}
    private HashMap<Integer, LinkedHashSet<Integer>> byFreq = new HashMap<>(); // counter -> keys, LRU first

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

    private void touch(int key) {
        int[] n = node.get(key);
        int f = n[1];
        LinkedHashSet<Integer> l = byFreq.get(f);
        l.remove(key);
        if (l.isEmpty()) {
            byFreq.remove(f);
            if (minFreq == f) minFreq = f + 1;
        }
        n[1] = f + 1;
        byFreq.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
    }

    public int get(int key) {
        int[] n = node.get(key);
        if (n == null) return -1;
        touch(key);
        return n[0];
    }

    public void put(int key, int value) {
        int[] n = node.get(key);
        if (n != null) { n[0] = value; touch(key); return; }
        if (node.size() == cap) {
            LinkedHashSet<Integer> l = byFreq.get(minFreq);
            int old = l.iterator().next();
            l.remove(old);
            if (l.isEmpty()) byFreq.remove(minFreq);
            node.remove(old);
        }
        node.put(key, new int[]{value, 1});
        byFreq.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
}

C++

class LFUCache {
    struct Item { int value, freq; list<int>::iterator pos; };
    int cap, minFreq = 0;
    unordered_map<int, Item> node;         // key -> value, counter, place in its list
    unordered_map<int, list<int>> byFreq;  // counter -> keys, least recently used first

    void touch(Item& it, int key) {
        int f = it.freq;
        list<int>& l = byFreq[f];
        l.erase(it.pos);
        if (l.empty()) {
            byFreq.erase(f);
            if (minFreq == f) minFreq = f + 1;
        }
        it.freq = f + 1;
        list<int>& nl = byFreq[f + 1];
        it.pos = nl.insert(nl.end(), key);
    }
public:
    LFUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto f = node.find(key);
        if (f == node.end()) return -1;
        touch(f->second, key);
        return f->second.value;
    }

    void put(int key, int value) {
        auto f = node.find(key);
        if (f != node.end()) { f->second.value = value; touch(f->second, key); return; }
        if ((int)node.size() == cap) {
            list<int>& l = byFreq[minFreq];
            int old = l.front();
            l.pop_front();
            if (l.empty()) byFreq.erase(minFreq);
            node.erase(old);
        }
        list<int>& l1 = byFreq[1];
        node[key] = Item{value, 1, l1.insert(l1.end(), key)};
        minFreq = 1;
    }
};

JavaScript

// A Map iterates in insertion order, so each counter's Map of keys is an LRU list.
var LFUCache = function(capacity) {
    this.cap = capacity;
    this.node = new Map();   // key -> { value, freq }
    this.byFreq = new Map(); // counter -> Map of keys, least recently used first
    this.minFreq = 0;
};

LFUCache.prototype.listOf = function(f) {
    var l = this.byFreq.get(f);
    if (!l) { l = new Map(); this.byFreq.set(f, l); }
    return l;
};

LFUCache.prototype.touch = function(key) {
    var n = this.node.get(key), f = n.freq, l = this.byFreq.get(f);
    l.delete(key);
    if (l.size === 0) {
        this.byFreq.delete(f);
        if (this.minFreq === f) this.minFreq = f + 1;
    }
    n.freq = f + 1;
    this.listOf(f + 1).set(key, true);
};

LFUCache.prototype.get = function(key) {
    var n = this.node.get(key);
    if (!n) return -1;
    this.touch(key);
    return n.value;
};

LFUCache.prototype.put = function(key, value) {
    var n = this.node.get(key);
    if (n) { n.value = value; this.touch(key); return; }
    if (this.node.size === this.cap) {
        var l = this.byFreq.get(this.minFreq);
        var old = l.keys().next().value;
        l.delete(old);
        if (l.size === 0) this.byFreq.delete(this.minFreq);
        this.node.delete(old);
    }
    this.node.set(key, { value: value, freq: 1 });
    this.listOf(1).set(key, true);
    this.minFreq = 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Design Movie Rental System Hard
• Dinner Plate Stacks Hard
• Prefix and Suffix Search Hard
• Vertical Order Traversal of a Binary Tree Hard
• Maximum Number of Ways to Partition an Array Hard
• Sum of Imbalance Numbers of All Subarrays Hard