LFU Cache

Editorial

Core insight

LFU Cache · Design Patterns

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:

Frequency Map: A HashMap mapping frequency -> DoublyLinkedList. This gives us $O(1)$ access to all keys with a specific access count.
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.
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.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 460: LFU Cache Solution & Explanation

Problem Overview

TL;DR: To achieve $O(1)$ complexity for LFU operations, we utilize two HashMaps: one to map keys to values/metadata, and another to map frequency counts to doubly linked lists containing the keys.

The LeetCode 460 problem asks us to design a Least Frequently Used (LFU) cache. Unlike a standard cache that evicts the oldest item, an LFU cache tracks how often an item is accessed. When the cache reaches its capacity, it must invalidate the key with the lowest access frequency. If multiple keys share the same lowest frequency, the tie is broken by invalidating the least recently used (LRU) key among them.

The critical constraint is that both get and put operations must run in $O(1)$ average time complexity. This eliminates solutions based on sorting or standard heaps.

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.

Storage: Use a HashMap to store key -> value.
Metadata: Use a list or array to store objects containing {key, frequency, last_accessed_time}.
Get: Search the list for the key, update its frequency and timestamp.
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

1# Naive LFU
2def put(key, value):
3    if key in cache:
4        update_freq(key)
5        cache[key] = value
6    else:
7        if len(cache) >= capacity:
8            # Linear scan to find victim
9            victim = find_min_freq_and_lru() # O(N)
10            remove(victim)
11        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)$ .

Algorithm Strategy: Design Patterns

We will implement the solution using two HashMaps and a custom Doubly Linked List class.

Data Structures:
- Node: Stores key, value, frequency, prev, and next.
- DoublyLinkedList: Helper class to manage a list of Nodes. Needs methods to addNode (to head), removeNode (arbitrary), and removeTail (for eviction).
- keyTable: HashMap<Integer, Node> mapping keys to their node instances.
- freqTable: HashMap<Integer, DoublyLinkedList> mapping frequencies to lists of nodes.
- minFreq: Integer tracking the minimum frequency.
- capacity: Integer.
Helper Function: updateFreq(node)
- This function is called whenever get or put accesses an existing key.
- It retrieves the node's current frequency f.
- It removes the node from the DLL at freqTable[f].
- Crucial Step: If freqTable[f] is empty and f == minFreq, increment minFreq. (We know the next min must be f+1 because we just moved a node there, or there are other nodes at higher frequencies).
- Increment the node's frequency to f+1.
- Add the node to freqTable[f+1].
Operation: get(key)
- If key not in keyTable, return -1.
- Get the node. Call updateFreq(node).
- Return node.value.
Operation: put(key, value)
- If capacity == 0, return immediately.
- If key exists:
  - Get node. Update node.value. Call updateFreq(node).
- If key does not exist:
  - Check if size == capacity.
  - If full:
    - Get the DLL at freqTable[minFreq].
    - Remove the tail (LRU) of that DLL.
    - Remove the corresponding entry from keyTable.
  - Create a new Node(key, value, freq=1).
  - Add to keyTable.
  - Add to freqTable[1].
  - Reset minFreq to 1.

Execution Flow

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

Initialize: minFreq = 0, capacity = 2, Tables empty.
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]}.
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]}.
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.
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:

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.
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.

Pattern Reuse Notes

The Design (General/Specific) pattern used here is highly transferable to other system design and data structure problems.

LeetCode 146: LRU Cache: This is a subset of LFU. It uses a single Doubly Linked List and a HashMap. The logic for moving nodes to the head (MRU) is identical to the logic inside one frequency bucket of the LFU cache.
LeetCode 155: Min Stack: Requires tracking the minimum element in $O(1)$ . Similar to tracking minFreq, this uses an auxiliary stack (or value pairing) to maintain state efficiently.
LeetCode 225: Implement Stack using Queues: Manipulating standard data structures to achieve specific behavioral constraints.
LeetCode 232: Implement Queue using Stacks: Similar to the above, emphasizing the composition of basic structures to satisfy interface requirements.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 460

cpp

1#include <unordered_map>
2#include <list>
3
4using namespace std;
5
6class LFUCache {
7    struct Node {
8        int key;
9        int value;
10        int freq;
11        // Iterators are used to delete from list in O(1)
12        list<int>::iterator itr; 
13    };
14
15    int capacity;
16    int minFreq;
17    
18    // key -> Node
19    unordered_map<int, Node> keyTable;
20    // freq -> List of keys (Doubly Linked List via std::list)
21    unordered_map<int, list<int>> freqTable;
22    // key -> Iterator in the freqTable list (to enable O(1) removal)
23    unordered_map<int, list<int>::iterator> keyIterTable;
24
25public:
26    LFUCache(int capacity) {
27        this->capacity = capacity;
28        this->minFreq = 0;
29    }
30
31    int get(int key) {
32        if (keyTable.find(key) == keyTable.end()) {
33            return -1;
34        }
35        
36        Node& node = keyTable[key];
37        updateFreq(node);
38        return node.value;
39    }
40
41    void put(int key, int value) {
42        if (capacity == 0) return;
43
44        if (keyTable.find(key) != keyTable.end()) {
45            Node& node = keyTable[key];
46            node.value = value;
47            updateFreq(node);
48            return;
49        }
50
51        if (keyTable.size() == capacity) {
52            // Evict LFU (and LRU within that freq)
53            list<int>& lfuList = freqTable[minFreq];
54            int evictKey = lfuList.back();
55            lfuList.pop_back();
56            
57            keyTable.erase(evictKey);
58            keyIterTable.erase(evictKey);
59        }
60
61        // Insert new
62        minFreq = 1;
63        freqTable[1].push_front(key);
64        keyIterTable[key] = freqTable[1].begin();
65        keyTable[key] = {key, value, 1}; // iterator is handled separately in C++ due to struct copy
66    }
67
68private:
69    void updateFreq(Node& node) {
70        int prevFreq = node.freq;
71        
72        // Remove from old freq list
73        freqTable[prevFreq].erase(keyIterTable[node.key]);
74        
75        // Update minFreq if necessary
76        if (freqTable[prevFreq].empty()) {
77            freqTable.erase(prevFreq);
78            if (minFreq == prevFreq) {
79                minFreq++;
80            }
81        }
82        
83        // Add to new freq list
84        node.freq++;
85        freqTable[node.freq].push_front(node.key);
86        keyIterTable[node.key] = freqTable[node.freq].begin();
87    }
88};

Java Solution for LeetCode 460

java

1import java.util.HashMap;
2import java.util.Map;
3
4class LFUCache {
5
6    // Custom Doubly Linked List Node
7    class Node {
8        int key, value, freq;
9        Node prev, next;
10        
11        Node(int key, int value) {
12            this.key = key;
13            this.value = value;
14            this.freq = 1;
15        }
16    }
17
18    // Custom Doubly Linked List
19    class DoublyLinkedList {
20        Node head, tail;
21        int size;
22        
23        DoublyLinkedList() {
24            head = new Node(0, 0);
25            tail = new Node(0, 0);
26            head.next = tail;
27            tail.prev = head;
28            size = 0;
29        }
30        
31        void addHead(Node node) {
32            Node next = head.next;
33            head.next = node;
34            node.prev = head;
35            node.next = next;
36            next.prev = node;
37            size++;
38        }
39        
40        void removeNode(Node node) {
41            Node prev = node.prev;
42            Node next = node.next;
43            prev.next = next;
44            next.prev = prev;
45            size--;
46        }
47        
48        Node removeTail() {
49            if (size > 0) {
50                Node node = tail.prev;
51                removeNode(node);
52                return node;
53            }
54            return null;
55        }
56    }
57
58    int capacity;
59    int minFreq;
60    Map<Integer, Node> keyTable;
61    Map<Integer, DoublyLinkedList> freqTable;
62
63    public LFUCache(int capacity) {
64        this.capacity = capacity;
65        this.minFreq = 0;
66        this.keyTable = new HashMap<>();
67        this.freqTable = new HashMap<>();
68    }
69    
70    public int get(int key) {
71        Node node = keyTable.get(key);
72        if (node == null) return -1;
73        
74        updateFreq(node);
75        return node.value;
76    }
77    
78    public void put(int key, int value) {
79        if (capacity == 0) return;
80        
81        if (keyTable.containsKey(key)) {
82            Node node = keyTable.get(key);
83            node.value = value;
84            updateFreq(node);
85            return;
86        }
87        
88        if (keyTable.size() == capacity) {
89            DoublyLinkedList minList = freqTable.get(minFreq);
90            Node toEvict = minList.removeTail();
91            keyTable.remove(toEvict.key);
92        }
93        
94        Node newNode = new Node(key, value);
95        keyTable.put(key, newNode);
96        minFreq = 1;
97        
98        freqTable.putIfAbsent(1, new DoublyLinkedList());
99        freqTable.get(1).addHead(newNode);
100    }
101    
102    private void updateFreq(Node node) {
103        int curFreq = node.freq;
104        DoublyLinkedList list = freqTable.get(curFreq);
105        list.removeNode(node);
106        
107        if (curFreq == minFreq && list.size == 0) {
108            minFreq++;
109        }
110        
111        node.freq++;
112        freqTable.putIfAbsent(node.freq, new DoublyLinkedList());
113        freqTable.get(node.freq).addHead(node);
114    }
115}

Python Solution for LeetCode 460

python

1class Node:
2    def __init__(self, key, value):
3        self.key = key
4        self.value = value
5        self.freq = 1
6        self.prev = None
7        self.next = None
8
9class DoublyLinkedList:
10    def __init__(self):
11        self.head = Node(0, 0) # Dummy head
12        self.tail = Node(0, 0) # Dummy tail
13        self.head.next = self.tail
14        self.tail.prev = self.head
15        self.size = 0
16        
17    def add_node(self, node):
18        # Add to head (MRU)
19        next_node = self.head.next
20        self.head.next = node
21        node.prev = self.head
22        node.next = next_node
23        next_node.prev = node
24        self.size += 1
25        
26    def remove_node(self, node):
27        prev_node = node.prev
28        next_node = node.next
29        prev_node.next = next_node
30        next_node.prev = prev_node
31        self.size -= 1
32        
33    def remove_tail(self):
34        # Remove LRU
35        if self.size == 0:
36            return None
37        node = self.tail.prev
38        self.remove_node(node)
39        return node
40
41class LFUCache:
42
43    def __init__(self, capacity: int):
44        self.capacity = capacity
45        self.min_freq = 0
46        self.key_table = {} # key -> Node
47        self.freq_table = {} # freq -> DoublyLinkedList
48
49    def _update_freq(self, node):
50        # Remove from current freq list
51        freq = node.freq
52        self.freq_table[freq].remove_node(node)
53        
54        # If this list is empty and was the min_freq, increment min_freq
55        if freq == self.min_freq and self.freq_table[freq].size == 0:
56            self.min_freq += 1
57            
58        # Add to new freq list
59        node.freq += 1
60        new_freq = node.freq
61        if new_freq not in self.freq_table:
62            self.freq_table[new_freq] = DoublyLinkedList()
63        self.freq_table[new_freq].add_node(node)
64
65    def get(self, key: int) -> int:
66        if key not in self.key_table:
67            return -1
68        
69        node = self.key_table[key]
70        self._update_freq(node)
71        return node.value
72
73    def put(self, key: int, value: int) -> None:
74        if self.capacity == 0:
75            return
76            
77        if key in self.key_table:
78            node = self.key_table[key]
79            node.value = value
80            self._update_freq(node)
81            return
82        
83        if len(self.key_table) == self.capacity:
84            # Evict
85            lfu_list = self.freq_table[self.min_freq]
86            evicted_node = lfu_list.remove_tail()
87            del self.key_table[evicted_node.key]
88            
89        # Create new
90        new_node = Node(key, value)
91        self.key_table[key] = new_node
92        self.min_freq = 1
93        
94        if 1 not in self.freq_table:
95            self.freq_table[1] = DoublyLinkedList()
96        self.freq_table[1].add_node(new_node)

Editorial

Core insight

LFU Cache · Design Patterns

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.

Key Invariants:

Frequency Map: A HashMap mapping frequency -> DoublyLinkedList. This gives us $O(1)$ access to all keys with a specific access count.
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.
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.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 460: LFU Cache Solution & Explanation

Problem Overview

The critical constraint is that both get and put operations must run in $O(1)$ average time complexity. This eliminates solutions based on sorting or standard heaps.

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.

Storage: Use a HashMap to store key -> value.
Metadata: Use a list or array to store objects containing {key, frequency, last_accessed_time}.
Get: Search the list for the key, update its frequency and timestamp.
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

1# Naive LFU
2def put(key, value):
3    if key in cache:
4        update_freq(key)
5        cache[key] = value
6    else:
7        if len(cache) >= capacity:
8            # Linear scan to find victim
9            victim = find_min_freq_and_lru() # O(N)
10            remove(victim)
11        add_new(key, value)

Algorithm Strategy: Design Patterns

We will implement the solution using two HashMaps and a custom Doubly Linked List class.

Data Structures:
- Node: Stores key, value, frequency, prev, and next.
- DoublyLinkedList: Helper class to manage a list of Nodes. Needs methods to addNode (to head), removeNode (arbitrary), and removeTail (for eviction).
- keyTable: HashMap<Integer, Node> mapping keys to their node instances.
- freqTable: HashMap<Integer, DoublyLinkedList> mapping frequencies to lists of nodes.
- minFreq: Integer tracking the minimum frequency.
- capacity: Integer.
Helper Function: updateFreq(node)
- This function is called whenever get or put accesses an existing key.
- It retrieves the node's current frequency f.
- It removes the node from the DLL at freqTable[f].
- Crucial Step: If freqTable[f] is empty and f == minFreq, increment minFreq. (We know the next min must be f+1 because we just moved a node there, or there are other nodes at higher frequencies).
- Increment the node's frequency to f+1.
- Add the node to freqTable[f+1].
Operation: get(key)
- If key not in keyTable, return -1.
- Get the node. Call updateFreq(node).
- Return node.value.
Operation: put(key, value)
- If capacity == 0, return immediately.
- If key exists:
  - Get node. Update node.value. Call updateFreq(node).
- If key does not exist:
  - Check if size == capacity.
  - If full:
    - Get the DLL at freqTable[minFreq].
    - Remove the tail (LRU) of that DLL.
    - Remove the corresponding entry from keyTable.
  - Create a new Node(key, value, freq=1).
  - Add to keyTable.
  - Add to freqTable[1].
  - Reset minFreq to 1.

Execution Flow

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

Initialize: minFreq = 0, capacity = 2, Tables empty.
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]}.
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]}.
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.
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:

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.
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.

Pattern Reuse Notes

The Design (General/Specific) pattern used here is highly transferable to other system design and data structure problems.

LeetCode 146: LRU Cache: This is a subset of LFU. It uses a single Doubly Linked List and a HashMap. The logic for moving nodes to the head (MRU) is identical to the logic inside one frequency bucket of the LFU cache.
LeetCode 155: Min Stack: Requires tracking the minimum element in $O(1)$ . Similar to tracking minFreq, this uses an auxiliary stack (or value pairing) to maintain state efficiently.
LeetCode 225: Implement Stack using Queues: Manipulating standard data structures to achieve specific behavioral constraints.
LeetCode 232: Implement Queue using Stacks: Similar to the above, emphasizing the composition of basic structures to satisfy interface requirements.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 460

cpp

1#include <unordered_map>
2#include <list>
3
4using namespace std;
5
6class LFUCache {
7    struct Node {
8        int key;
9        int value;
10        int freq;
11        // Iterators are used to delete from list in O(1)
12        list<int>::iterator itr; 
13    };
14
15    int capacity;
16    int minFreq;
17    
18    // key -> Node
19    unordered_map<int, Node> keyTable;
20    // freq -> List of keys (Doubly Linked List via std::list)
21    unordered_map<int, list<int>> freqTable;
22    // key -> Iterator in the freqTable list (to enable O(1) removal)
23    unordered_map<int, list<int>::iterator> keyIterTable;
24
25public:
26    LFUCache(int capacity) {
27        this->capacity = capacity;
28        this->minFreq = 0;
29    }
30
31    int get(int key) {
32        if (keyTable.find(key) == keyTable.end()) {
33            return -1;
34        }
35        
36        Node& node = keyTable[key];
37        updateFreq(node);
38        return node.value;
39    }
40
41    void put(int key, int value) {
42        if (capacity == 0) return;
43
44        if (keyTable.find(key) != keyTable.end()) {
45            Node& node = keyTable[key];
46            node.value = value;
47            updateFreq(node);
48            return;
49        }
50
51        if (keyTable.size() == capacity) {
52            // Evict LFU (and LRU within that freq)
53            list<int>& lfuList = freqTable[minFreq];
54            int evictKey = lfuList.back();
55            lfuList.pop_back();
56            
57            keyTable.erase(evictKey);
58            keyIterTable.erase(evictKey);
59        }
60
61        // Insert new
62        minFreq = 1;
63        freqTable[1].push_front(key);
64        keyIterTable[key] = freqTable[1].begin();
65        keyTable[key] = {key, value, 1}; // iterator is handled separately in C++ due to struct copy
66    }
67
68private:
69    void updateFreq(Node& node) {
70        int prevFreq = node.freq;
71        
72        // Remove from old freq list
73        freqTable[prevFreq].erase(keyIterTable[node.key]);
74        
75        // Update minFreq if necessary
76        if (freqTable[prevFreq].empty()) {
77            freqTable.erase(prevFreq);
78            if (minFreq == prevFreq) {
79                minFreq++;
80            }
81        }
82        
83        // Add to new freq list
84        node.freq++;
85        freqTable[node.freq].push_front(node.key);
86        keyIterTable[node.key] = freqTable[node.freq].begin();
87    }
88};

Java Solution for LeetCode 460

java

1import java.util.HashMap;
2import java.util.Map;
3
4class LFUCache {
5
6    // Custom Doubly Linked List Node
7    class Node {
8        int key, value, freq;
9        Node prev, next;
10        
11        Node(int key, int value) {
12            this.key = key;
13            this.value = value;
14            this.freq = 1;
15        }
16    }
17
18    // Custom Doubly Linked List
19    class DoublyLinkedList {
20        Node head, tail;
21        int size;
22        
23        DoublyLinkedList() {
24            head = new Node(0, 0);
25            tail = new Node(0, 0);
26            head.next = tail;
27            tail.prev = head;
28            size = 0;
29        }
30        
31        void addHead(Node node) {
32            Node next = head.next;
33            head.next = node;
34            node.prev = head;
35            node.next = next;
36            next.prev = node;
37            size++;
38        }
39        
40        void removeNode(Node node) {
41            Node prev = node.prev;
42            Node next = node.next;
43            prev.next = next;
44            next.prev = prev;
45            size--;
46        }
47        
48        Node removeTail() {
49            if (size > 0) {
50                Node node = tail.prev;
51                removeNode(node);
52                return node;
53            }
54            return null;
55        }
56    }
57
58    int capacity;
59    int minFreq;
60    Map<Integer, Node> keyTable;
61    Map<Integer, DoublyLinkedList> freqTable;
62
63    public LFUCache(int capacity) {
64        this.capacity = capacity;
65        this.minFreq = 0;
66        this.keyTable = new HashMap<>();
67        this.freqTable = new HashMap<>();
68    }
69    
70    public int get(int key) {
71        Node node = keyTable.get(key);
72        if (node == null) return -1;
73        
74        updateFreq(node);
75        return node.value;
76    }
77    
78    public void put(int key, int value) {
79        if (capacity == 0) return;
80        
81        if (keyTable.containsKey(key)) {
82            Node node = keyTable.get(key);
83            node.value = value;
84            updateFreq(node);
85            return;
86        }
87        
88        if (keyTable.size() == capacity) {
89            DoublyLinkedList minList = freqTable.get(minFreq);
90            Node toEvict = minList.removeTail();
91            keyTable.remove(toEvict.key);
92        }
93        
94        Node newNode = new Node(key, value);
95        keyTable.put(key, newNode);
96        minFreq = 1;
97        
98        freqTable.putIfAbsent(1, new DoublyLinkedList());
99        freqTable.get(1).addHead(newNode);
100    }
101    
102    private void updateFreq(Node node) {
103        int curFreq = node.freq;
104        DoublyLinkedList list = freqTable.get(curFreq);
105        list.removeNode(node);
106        
107        if (curFreq == minFreq && list.size == 0) {
108            minFreq++;
109        }
110        
111        node.freq++;
112        freqTable.putIfAbsent(node.freq, new DoublyLinkedList());
113        freqTable.get(node.freq).addHead(node);
114    }
115}

Python Solution for LeetCode 460

python

1class Node:
2    def __init__(self, key, value):
3        self.key = key
4        self.value = value
5        self.freq = 1
6        self.prev = None
7        self.next = None
8
9class DoublyLinkedList:
10    def __init__(self):
11        self.head = Node(0, 0) # Dummy head
12        self.tail = Node(0, 0) # Dummy tail
13        self.head.next = self.tail
14        self.tail.prev = self.head
15        self.size = 0
16        
17    def add_node(self, node):
18        # Add to head (MRU)
19        next_node = self.head.next
20        self.head.next = node
21        node.prev = self.head
22        node.next = next_node
23        next_node.prev = node
24        self.size += 1
25        
26    def remove_node(self, node):
27        prev_node = node.prev
28        next_node = node.next
29        prev_node.next = next_node
30        next_node.prev = prev_node
31        self.size -= 1
32        
33    def remove_tail(self):
34        # Remove LRU
35        if self.size == 0:
36            return None
37        node = self.tail.prev
38        self.remove_node(node)
39        return node
40
41class LFUCache:
42
43    def __init__(self, capacity: int):
44        self.capacity = capacity
45        self.min_freq = 0
46        self.key_table = {} # key -> Node
47        self.freq_table = {} # freq -> DoublyLinkedList
48
49    def _update_freq(self, node):
50        # Remove from current freq list
51        freq = node.freq
52        self.freq_table[freq].remove_node(node)
53        
54        # If this list is empty and was the min_freq, increment min_freq
55        if freq == self.min_freq and self.freq_table[freq].size == 0:
56            self.min_freq += 1
57            
58        # Add to new freq list
59        node.freq += 1
60        new_freq = node.freq
61        if new_freq not in self.freq_table:
62            self.freq_table[new_freq] = DoublyLinkedList()
63        self.freq_table[new_freq].add_node(node)
64
65    def get(self, key: int) -> int:
66        if key not in self.key_table:
67            return -1
68        
69        node = self.key_table[key]
70        self._update_freq(node)
71        return node.value
72
73    def put(self, key: int, value: int) -> None:
74        if self.capacity == 0:
75            return
76            
77        if key in self.key_table:
78            node = self.key_table[key]
79            node.value = value
80            self._update_freq(node)
81            return
82        
83        if len(self.key_table) == self.capacity:
84            # Evict
85            lfu_list = self.freq_table[self.min_freq]
86            evicted_node = lfu_list.remove_tail()
87            del self.key_table[evicted_node.key]
88            
89        # Create new
90        new_node = Node(key, value)
91        self.key_table[key] = new_node
92        self.min_freq = 1
93        
94        if 1 not in self.freq_table:
95            self.freq_table[1] = DoublyLinkedList()
96        self.freq_table[1].add_node(new_node)

Core insight

Core Insight for LFU Cache

Full breakdown

LeetCode 460: LFU Cache Solution & Explanation

Problem Overview

Brute Force Approach for LFU Cache

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 460

Java Solution for LeetCode 460

Python Solution for LeetCode 460

Practise LFU Cache and the problems around it

Related problems

LFU Cache

Core insight

Core Insight for LFU Cache

Full breakdown

LeetCode 460: LFU Cache Solution & Explanation

Problem Overview

Brute Force Approach for LFU Cache

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 460

Java Solution for LeetCode 460

Python Solution for LeetCode 460

Practise LFU Cache and the problems around it

Related problems