Brute Force Approach for LFU Cache

A naive approach to solving the LFU Cache problem focuses on storing the data and searching for the eviction candidate linearly.

1. Storage: Use a HashMap to store key -> value.
2. Metadata: Use a list or array to store objects containing {key, frequency, last_accessed_time}.
3. Get: Search the list for the key, update its frequency and timestamp.
4. Put: If the key exists, update it. If not, and the cache is full, iterate through the entire list to find the element with the minimum frequency (and oldest timestamp for ties). Remove it and insert the new item.

Pseudo-code:

python
# Naive LFU
def put(key, value):
    if key in cache:
        update_freq(key)
        cache[key] = value
    else:
        if len(cache) >= capacity:
            # Linear scan to find victim
            victim = find_min_freq_and_lru() # O(N)
            remove(victim)
        add_new(key, value)

Complexity Analysis: The get operation can be $O(1)$ with a HashMap, but the put operation (specifically the eviction step) requires scanning all $N$ elements to find the minimum frequency. This results in $O(N)$ time complexity.

Why it fails: Given the constraint $N \le 10^5$ and $2 \times 10^5$ calls, an $O(N)$ operation per call results in $O(N^2)$ total operations, which will strictly trigger a Time Limit Exceeded (TLE) error. The solution must be $O(1)$.

Core Insight for LFU Cache

The core insight to bridge the gap between the brute force $O(N)$ approach and the required $O(1)$ solution is to bucketize the keys based on their frequency.

Instead of searching for the minimum frequency, we can maintain lists of keys for every frequency currently in the cache. Since frequencies only increment by 1, we can move keys between these lists efficiently.

To handle the "Least Recently Used" tie-breaker within a specific frequency, each bucket should be a Doubly Linked List (DLL). DLLs allow us to remove a node from anywhere in $O(1)$ (if we have a reference to it) and add to the head/tail in $O(1)$.

Key Invariants:

1. Frequency Map: A HashMap mapping frequency -> DoublyLinkedList. This gives us $O(1)$ access to all keys with a specific access count.
2. Key Map: A HashMap mapping key -> Node. The Node stores the value, the key, its current frequency, and pointers to its position in the DLL. This allows us to jump directly to a node to update it without traversing a list.
3. Min Frequency Tracker: A simple integer variable minFreq that tracks the current lowest frequency in the cache. This allows us to determine which bucket to evict from in $O(1)$ time without searching.

Visual Description: Imagine a vertical column of buckets labeled 1, 2, 3, etc.

• When a new key is added, it drops into bucket 1. minFreq is set to 1.
• When an existing key is accessed, we lift it out of bucket k and drop it into bucket k+1.
• If bucket k becomes empty and k was the minFreq, we increment minFreq.
• When we need to evict, we go to the bucket labeled minFreq, take the item at the bottom (LRU), and remove it.

Execution Flow

Let's trace capacity = 2, put(1, 1), put(2, 2), get(1), put(3, 3).

1. Initialize: minFreq = 0, capacity = 2, Tables empty.
2. put(1, 1):
   • Cache not full. New key.
   • Create Node 1. Freq = 1.
   • Add to freqTable[1].
   • minFreq = 1.
   • State: keyTable={1: Node1}, freqTable={1: [Node1]}.
3. put(2, 2):
   • Cache not full. New key.
   • Create Node 2. Freq = 1.
   • Add to freqTable[1]. (Added to head, so Node 2 is MRU, Node 1 is LRU in this bucket).
   • minFreq = 1.
   • State: keyTable={1: Node1, 2: Node2}, freqTable={1: [Node2, Node1]}.
4. get(1):
   • Found Node 1.
   • Update Freq:
     • Remove Node 1 from freqTable[1]. List at 1 is now [Node2].
     • minFreq is 1. List is not empty, so minFreq stays 1.
     • Node 1 freq becomes 2.
     • Add Node 1 to freqTable[2].
   • State: keyTable={...}, freqTable={1: [Node2], 2: [Node1]}, minFreq=1.
5. put(3, 3):
   • Cache is full (size 2). Eviction needed.
   • Look at freqTable[minFreq] (which is freqTable[1]).
   • List is [Node2]. Tail is Node 2.
   • Remove Node 2 from keyTable and freqTable.
   • Create Node 3. Freq = 1.
   • Add to freqTable[1].
   • minFreq = 1.
   • State: keyTable={1: Node1, 3: Node3}, freqTable={1: [Node3], 2: [Node1]}, minFreq=1.

Proof of Correctness

The algorithm maintains correctness through two main invariants:

1. LFU Invariant: The minFreq variable strictly tracks the lowest existing frequency. When we insert a new element, it becomes 1. When we promote an element from minFreq to minFreq + 1, we only update minFreq if the bucket at minFreq becomes empty. This guarantees freqTable[minFreq] always contains the candidates for eviction.
2. LRU Tie-breaking Invariant: Within each freqTable bucket, we use a Doubly Linked List. We always add recently accessed/modified nodes to the head. Therefore, the tail is always the Least Recently Used node for that specific frequency. Evicting the tail of freqTable[minFreq] satisfies the tie-breaking condition.

Reference Implementation

C++ Solution for LeetCode 460

cpp
#include <unordered_map>
#include <list>

using namespace std;

class LFUCache {
    struct Node {
        int key;
        int value;
        int freq;
        // Iterators are used to delete from list in O(1)
        list<int>::iterator itr; 
    };

    int capacity;
    int minFreq;
    
    // key -> Node
    unordered_map<int, Node> keyTable;
    // freq -> List of keys (Doubly Linked List via std::list)
    unordered_map<int, list<int>> freqTable;
    // key -> Iterator in the freqTable list (to enable O(1) removal)
    unordered_map<int, list<int>::iterator> keyIterTable;

public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        this->minFreq = 0;
    }

    int get(int key) {
        if (keyTable.find(key) == keyTable.end()) {
            return -1;
        }
        
        Node& node = keyTable[key];
        updateFreq(node);
        return node.value;
    }

    void put(int key, int value) {
        if (capacity == 0) return;

        if (keyTable.find(key) != keyTable.end()) {
            Node& node = keyTable[key];
            node.value = value;
            updateFreq(node);
            return;
        }

        if (keyTable.size() == capacity) {
            // Evict LFU (and LRU within that freq)
            list<int>& lfuList = freqTable[minFreq];
            int evictKey = lfuList.back();
            lfuList.pop_back();
            
            keyTable.erase(evictKey);
            keyIterTable.erase(evictKey);
        }

        // Insert new
        minFreq = 1;
        freqTable[1].push_front(key);
        keyIterTable[key] = freqTable[1].begin();
        keyTable[key] = {key, value, 1}; // iterator is handled separately in C++ due to struct copy
    }

private:
    void updateFreq(Node& node) {
        int prevFreq = node.freq;
        
        // Remove from old freq list
        freqTable[prevFreq].erase(keyIterTable[node.key]);
        
        // Update minFreq if necessary
        if (freqTable[prevFreq].empty()) {
            freqTable.erase(prevFreq);
            if (minFreq == prevFreq) {
                minFreq++;
            }
        }
        
        // Add to new freq list
        node.freq++;
        freqTable[node.freq].push_front(node.key);
        keyIterTable[node.key] = freqTable[node.freq].begin();
    }
};

Java Solution for LeetCode 460

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

class LFUCache {

    // Custom Doubly Linked List Node
    class Node {
        int key, value, freq;
        Node prev, next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1;
        }
    }

    // Custom Doubly Linked List
    class DoublyLinkedList {
        Node head, tail;
        int size;
        
        DoublyLinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }
        
        void addHead(Node node) {
            Node next = head.next;
            head.next = node;
            node.prev = head;
            node.next = next;
            next.prev = node;
            size++;
        }
        
        void removeNode(Node node) {
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            size--;
        }
        
        Node removeTail() {
            if (size > 0) {
                Node node = tail.prev;
                removeNode(node);
                return node;
            }
            return null;
        }
    }

    int capacity;
    int minFreq;
    Map<Integer, Node> keyTable;
    Map<Integer, DoublyLinkedList> freqTable;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyTable = new HashMap<>();
        this.freqTable = new HashMap<>();
    }
    
    public int get(int key) {
        Node node = keyTable.get(key);
        if (node == null) return -1;
        
        updateFreq(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) return;
        
        if (keyTable.containsKey(key)) {
            Node node = keyTable.get(key);
            node.value = value;
            updateFreq(node);
            return;
        }
        
        if (keyTable.size() == capacity) {
            DoublyLinkedList minList = freqTable.get(minFreq);
            Node toEvict = minList.removeTail();
            keyTable.remove(toEvict.key);
        }
        
        Node newNode = new Node(key, value);
        keyTable.put(key, newNode);
        minFreq = 1;
        
        freqTable.putIfAbsent(1, new DoublyLinkedList());
        freqTable.get(1).addHead(newNode);
    }
    
    private void updateFreq(Node node) {
        int curFreq = node.freq;
        DoublyLinkedList list = freqTable.get(curFreq);
        list.removeNode(node);
        
        if (curFreq == minFreq && list.size == 0) {
            minFreq++;
        }
        
        node.freq++;
        freqTable.putIfAbsent(node.freq, new DoublyLinkedList());
        freqTable.get(node.freq).addHead(node);
    }
}

Python Solution for LeetCode 460

python
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(0, 0) # Dummy head
        self.tail = Node(0, 0) # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
        
    def add_node(self, node):
        # Add to head (MRU)
        next_node = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = next_node
        next_node.prev = node
        self.size += 1
        
    def remove_node(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
        self.size -= 1
        
    def remove_tail(self):
        # Remove LRU
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove_node(node)
        return node

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_table = {} # key -> Node
        self.freq_table = {} # freq -> DoublyLinkedList

    def _update_freq(self, node):
        # Remove from current freq list
        freq = node.freq
        self.freq_table[freq].remove_node(node)
        
        # If this list is empty and was the min_freq, increment min_freq
        if freq == self.min_freq and self.freq_table[freq].size == 0:
            self.min_freq += 1
            
        # Add to new freq list
        node.freq += 1
        new_freq = node.freq
        if new_freq not in self.freq_table:
            self.freq_table[new_freq] = DoublyLinkedList()
        self.freq_table[new_freq].add_node(node)

    def get(self, key: int) -> int:
        if key not in self.key_table:
            return -1
        
        node = self.key_table[key]
        self._update_freq(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
            
        if key in self.key_table:
            node = self.key_table[key]
            node.value = value
            self._update_freq(node)
            return
        
        if len(self.key_table) == self.capacity:
            # Evict
            lfu_list = self.freq_table[self.min_freq]
            evicted_node = lfu_list.remove_tail()
            del self.key_table[evicted_node.key]
            
        # Create new
        new_node = Node(key, value)
        self.key_table[key] = new_node
        self.min_freq = 1
        
        if 1 not in self.freq_table:
            self.freq_table[1] = DoublyLinkedList()
        self.freq_table[1].add_node(new_node)