460 - LFU Cache

Problem

Design a Least Frequently Used (LFU) cache.

• LFUCache(int capacity) initialises the object with the capacity
• int get(int key) returns the value of the key if it exists, otherwise -1
• void put(int key, int value) updates the value if the key exists, otherwise inserts it. If the cache is at capacity, evict the least frequently used key first. On a tie, evict the least recently used of them.

Both get and put count as a use of the key. Both must run in O(1) average time.

["LFUCache","put","put","get","put","get","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]

Output: [null,null,null,1,null,-1,3,null,-1,3,4]

Constraints:

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

Approach

Use one list per count instead. Each list holds only the keys with that exact count, ordered by recency:

count 1:  [d] [c]          d was used more recently than c
count 2:  [a]
count 5:  [b]

minFreq = 1    ->  evict the back of list 1  ->  c

Within a list, the ordering is recency, so the tie-break works the same way it does in 146. Across lists, the key to evict is the back node of the lowest non-empty list.

So the only new problem is finding the lowest non-empty list in O(1). Scanning for it is O(number of distinct counts). Instead keep it in a variable minFreq and update it, which works because minFreq changes in exactly two situations:

• a new key is inserted. Its count is 1, so minFreq = 1.
• the last key in the minFreq list is promoted out of it. That list is now empty and the key moved to minFreq + 1, so minFreq becomes minFreq + 1.

Nothing else moves it. Promoting a key out of a higher list does not. Promoting a key out of the minFreq list while other keys remain there does not. Eviction removes a key from the minFreq list, and if that empties it, the next insert sets minFreq = 1 anyway.

Three pieces of state:

freqList   count -> list of {key, value}, front is the most recently used at that count
keyMap     key   -> {count, iterator to that key's node}
minFreq    the lowest count with a non-empty list

keyMap stores the count next to the iterator so a promotion knows which list to remove from. Each node stores its key so eviction knows which keyMap entry to erase — same reason as in 146.

class LFUCache {
    int cap, minFreq;
    unordered_map<int, list<pair<int,int>>> freqList;                     // count -> {key,val}
    unordered_map<int, pair<int, list<pair<int,int>>::iterator>> keyMap;  // key   -> {count, node}

    void touch(int key) {
        auto& [f, it] = keyMap[key];
        int val = it->second;
        freqList[f].erase(it);
        if (freqList[f].empty()) {
            freqList.erase(f);
            if (minFreq == f) minFreq = f + 1;
        }
        f++;
        freqList[f].emplace_front(key, val);
        it = freqList[f].begin();
    }

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

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

    void put(int key, int value) {
        if (cap <= 0) return;
        auto it = keyMap.find(key);
        if (it != keyMap.end()) {
            it->second.second->second = value;
            touch(key);
            return;
        }
        if ((int)keyMap.size() == cap) {
            auto& lst = freqList[minFreq];
            keyMap.erase(lst.back().first);
            lst.pop_back();
            if (lst.empty()) freqList.erase(minFreq);
        }
        freqList[1].emplace_front(key, value);
        keyMap[key] = {1, freqList[1].begin()};
        minFreq = 1;
    }
};

touch does the same four steps for both get and put: erase the node from its current list, raise minFreq if that list just became empty, push the node to the front of the next list up, and store the new count and iterator. list::erase on an iterator you already hold is O(1), and so is emplace_front.

auto& [f, it] = keyMap[key] binds by reference, so f++ and it = freqList[f].begin() write back into the map entry. Binding by value instead leaves keyMap holding the old count and an iterator to a node that was just erased.

Growing freqList inside touch does not break the stored iterators. unordered_map invalidates its own iterators when it rehashes, but not references to the values it holds, and the list objects are not copied or moved. The list iterators in keyMap point into those lists and stay valid.

capacity 2

put(1,1)    count1: [1]                minFreq=1
put(2,2)    count1: [2,1]              minFreq=1
get(1) ->1  count1: [2]  count2: [1]   list 1 still has 2, so minFreq stays 1
put(3,3)    evict back of list 1 = 2
            count1: [3]  count2: [1]   minFreq=1
get(2) ->-1
get(3) ->3  count1: []   count2: [3,1] list 1 emptied, minFreq=2
put(4,4)    evict back of list 2 = 1   both have count 2, 1 is less recent
            count1: [4]  count2: [3]   minFreq=1
get(1) ->-1
get(3) ->3
get(4) ->4

Complexity

	time	space
get	O(1)	—
put	O(1)	—
total		O(capacity)