LFU Cache

Description

460. LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:

• LFUCache(int capacity) Initializes the object with the capacity of the data structure.
• int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
• void put(int key, int value) Updates the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key is invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented whenever a get or put operation is called on it.

The functions get and put must each run in $O(1)$ average time complexity.

Example 1:

Input:
["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]

Explanation:

// cnt(x) = the use counter for key x
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have cnt=2, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[4,3], cnt(4)=2, cnt(3)=3
 

Constraints:

• $1\le \text{capacity}\le 10^4$
• $0\le \text{key}\le 10^5$
• $0\le \text{value}\le 10^9$
• At most $2\times 10^5$ calls will be made to get and put.

---

Most Optimized Solution: Two Hash Maps + Frequency Doubly Linked Lists ($O(1)$)

Intuition

To achieve $O(1)$ time complexity for both get and put, we maintain:

1. keyNodeMap (Map<Integer, Node>): Maps a key directly to its corresponding DLL Node for $O(1)$ key lookup.
2. freqMap (Map<Integer, DoublyLinkedList>): Maps a frequency count to a Doubly Linked List containing all nodes with that exact frequency. Each frequency list acts as an LRU queue (head = MRU, tail = LRU).
3. minFreq: Tracks the global minimum frequency currently present in the cache.

When an element is accessed (get or updated put), its frequency increases by 1:

• We remove it from its current frequency list in freqMap.
• If that list becomes empty and its frequency was equal to minFreq, we increment minFreq.
• We then insert the node into the list for frequency + 1.

When the cache exceeds capacity during an insertion:

• We evict the least recently used node from the list at freqMap.get(minFreq).

import java.util.HashMap;
import java.util.Map;
 
class LFUCache {
 
    private class Node {
        int key;
        int val;
        int freq;
        Node prev;
        Node next;
 
        Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.freq = 1;
        }
    }
 
    private class DoublyLinkedList {
        Node head;
        Node tail;
        int size;
 
        DoublyLinkedList() {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }
 
        void addHead(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
            size++;
        }
 
        void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }
 
        Node removeTail() {
            if (size == 0) return null;
            Node lru = tail.prev;
            removeNode(lru);
            return lru;
        }
    }
 
    private final int capacity;
    private int minFreq;
    private final Map<Integer, Node> keyNodeMap;
    private final Map<Integer, DoublyLinkedList> freqMap;
 
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyNodeMap = new HashMap<>();
        this.freqMap = new HashMap<>();
    }
 
    public int get(int key) {
        if (!keyNodeMap.containsKey(key)) {
            return -1;
        }
        Node node = keyNodeMap.get(key);
        updateFreq(node);
        return node.val;
    }
 
    public void put(int key, int value) {
        if (capacity == 0) return;
 
        if (keyNodeMap.containsKey(key)) {
            Node node = keyNodeMap.get(key);
            node.val = value;
            updateFreq(node);
        } else {
            if (keyNodeMap.size() == capacity) {
                // Evict LFU item (and LRU tie-breaker) at minFreq
                DoublyLinkedList minList = freqMap.get(minFreq);
                Node evictedNode = minList.removeTail();
                keyNodeMap.remove(evictedNode.key);
            }
 
            // Insert new node
            Node newNode = new Node(key, value);
            minFreq = 1; // New node always starts with frequency 1
            keyNodeMap.put(key, newNode);
            freqMap.computeIfAbsent(1, k -> new DoublyLinkedList()).addHead(newNode);
        }
    }
 
    private void updateFreq(Node node) {
        int currentFreq = node.freq;
        DoublyLinkedList oldList = freqMap.get(currentFreq);
        oldList.removeNode(node);
 
        // Update minFreq if the emptied list was the minimum frequency
        if (currentFreq == minFreq && oldList.size == 0) {
            minFreq++;
        }
 
        node.freq++;
        freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList()).addHead(node);
    }
}
 

Complexity

• Time Complexity: $O(1)$ for both get and put operations.
• Space Complexity: $O(\text{capacity})$ to store up to capacity nodes across the hash maps and doubly linked lists.

---

Easy Memory Rule

“keyNodeMap finds the node in $O(1)$. freqMap groups nodes by frequency into LRU lists. On eviction, remove the tail node from freqMap.get(minFreq).”