The trick here is to name the state correctly, then let the implementation follow. For 460. LFU Cache, the solution in this repository is mainly a data structure design solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design, heap / priority queue.
The notes already sitting in the source point us in the right direction:
- heap + map
- TLE
- 20 / 23 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are operator, get, put, update, prepend.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: time = 0;
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//heap + map
02//TLE
03//20 / 23 test cases passed.
04struct FTV{
05 int freq;
06 int time;
07 int value;
08
09 FTV(int f, int t, int v){
10 freq = f;
11 time = t;
12 value = v;
13 }
14};
15
16class FTVCompare{
17public:
18 bool operator() (pair<int, FTV*>& a, pair<int, FTV*>& b) {
19 //the smaller freq, the smaller time will be evicted
20 return (a.second->freq == b.second->freq) ? a.second->time > b.second->time : a.second->freq > b.second->freq;
21 }
22};
23
24class LFUCache {
25public:
26 int capacity;
27 int time;
28
29 // std::function<bool (FTV*, FTV*)> comp = [](FTV* a, FTV* b){
30 // return (a->freq == b->freq) ? a->time < b->time : a->freq < b->freq;
31 // };
32 //(key, (freq, time, value))
33 priority_queue<pair<int, FTV*>, vector<pair<int, FTV*>>, FTVCompare> pq;
34
35 unordered_map<int, int> kvs;
36
37 LFUCache(int capacity) {
38 this->capacity = capacity;
39 time = 0;
40 }
41
42 int get(int key) {
43 if(kvs.find(key) == kvs.end()) return -1;
44 ++time;
45 // cout << "get (" << key << ")" << endl;
46 // cout << "there are " << kvs.size() << "(" << pq.size() << ") elements." << endl;
47 //don't need to update value, just update freq and time
48 update(key, -1);
49 return kvs[key];
50 }
51
52 void put(int key, int value) {
53 ++time;
54 if(capacity == 0) return;
55 //evict one
56 // cout << "put (" << key << ", " << value << ")" << endl;
57 // cout << "there are " << kvs.size() << "(" << pq.size() << ") elements." << endl;
58
59 if(kvs.find(key) != kvs.end()){
60 //update
61 update(key, value);
62 }else{
63 if(kvs.size() == capacity){
64 pair<int, FTV*> p = pq.top(); pq.pop();
65 kvs.erase(p.first);
66 // cout << "put " << key << ", evict " << p.first << endl;
67 }
68 //insert
69 kvs[key] = value;
70 pq.push({key, new FTV(1, time, value)});
71 }
72 }
73
74 void update(int key, int value){
75 if(value == -1) value = kvs[key];
76 kvs[key] = value;
77 priority_queue<pair<int, FTV*>, vector<pair<int, FTV*>>, FTVCompare> pq_tmp;
78 while(pq.top().first != key){
79 pair<int, FTV*> p = pq.top(); pq.pop();
80 pq_tmp.push(p);
81 }
82 pair<int, FTV*> p = pq.top(); pq.pop();
83 pq.push({p.first, new FTV(p.second->freq+1, time, value)});
84
85 while(!pq_tmp.empty()){
86 pair<int, FTV*> p = pq_tmp.top(); pq_tmp.pop();
87 pq.push(p);
88 }
89 }
90};
91
92/**
93 * Your LFUCache object will be instantiated and called as such:
94 * LFUCache* obj = new LFUCache(capacity);
95 * int param_1 = obj->get(key);
96 * obj->put(key,value);
97 */
98
99//double linked list + map
100//https://leetcode.com/problems/lfu-cache/discuss/207673/Python-concise-solution-**detailed**-explanation%3A-Two-dict-%2B-Doubly-linked-list
101//Runtime: 176 ms, faster than 97.79% of C++ online submissions for LFU Cache.
102//Memory Usage: 40.5 MB, less than 93.48% of C++ online submissions for LFU Cache.
103class DListNode{
104public:
105 int key;
106 int value;
107 int freq;
108 DListNode *prev, *next;
109
110 DListNode(int k, int v){
111 key = k;
112 value = v;
113 freq = 1;
114 prev = next = nullptr;
115 }
116};
117
118class DList{
119public:
120 DListNode* sentinel;
121 /*
122 sentinel->next points to the head of list,
123 sentinel->prev points to the tail of list
124 */
125 int size;
126
127 DList(){
128 size = 0;
129 //sentinel is a dummy node
130 sentinel = new DListNode(-1, -1);
131 sentinel->prev = sentinel->next = sentinel;
132 }
133
134 void prepend(DListNode* node){
135 //append to head
136 //update node itself
137 node->next = sentinel->next;
138 node->prev = sentinel;
139 //update node->next's prev
140 sentinel->next->prev = node;
141 //update node->prev's next
142 //node becomes head of list
143 sentinel->next = node;
144 ++size;
145 }
146
147 DListNode* pop(DListNode* node = nullptr){
148 if(size == 0) return nullptr;
149 //the last in the list
150 if(node == nullptr) node = sentinel->prev;
151 node->prev->next = node->next;
152 node->next->prev = node->prev;
153 --size;
154 return node;
155 }
156};
157
158class LFUCache {
159public:
160 //(key, node)
161 unordered_map<int, DListNode*> nodes;
162 //(freq, DList)
163 unordered_map<int, DList*> freqs;
164 int capacity;
165 int min_freq;
166
167 LFUCache(int capacity) {
168 this->capacity = capacity;
169 min_freq = 0;
170 }
171
172 void _update(DListNode* node){
173 //update the node's freq, freq list and min_freq
174 if(freqs.find(node->freq) == freqs.end()){
175 freqs[node->freq] = new DList();
176 }
177 if(freqs.find(node->freq+1) == freqs.end()){
178 freqs[node->freq+1] = new DList();
179 }
180 // cout << "pop from freqs[" << node->freq << "]" << endl;
181 freqs[node->freq]->pop(node);
182 if(min_freq == node->freq && freqs[node->freq]->size == 0){
183 ++min_freq;
184 }
185
186 ++node->freq;
187 // cout << "prepend to freqs[" << node->freq << "]" << endl;
188 freqs[node->freq]->prepend(node);
189 }
190
191 int get(int key) {
192 // cout << "get " << key << endl;
193 if(nodes.find(key) == nodes.end()){
194 return -1;
195 }
196
197 DListNode* node = nodes[key];
198
199 //update the node's freq, freq list and min_freq
200 _update(node);
201
202 return node->value;
203 }
204
205 void put(int key, int value) {
206 if(capacity == 0) return;
207 // cout << "put (" << key << ", " << value << ")" << endl;
208 if(nodes.find(key) != nodes.end()){
209 DListNode* node = nodes[key];
210 //update the node's freq, freq list and min_freq
211 _update(node);
212 //the node's value is also needed to be updated!
213 node->value = value;
214 }else{
215 if(nodes.size() == capacity){
216 if(freqs.find(min_freq) == freqs.end()){
217 freqs[min_freq] = new DList();
218 }
219
220 // cout << "freqs[" << min_freq << "]: ";
221 // DListNode* cur = freqs[min_freq]->sentinel->next;
222 // while(cur != freqs[min_freq]->sentinel){
223 // cout << "(" << cur->key << ", " << cur->value << ") ";
224 // cur = cur->next;
225 // }
226 // cout << endl;
227
228 //delete the node from freq list and the map
229 DListNode* node = freqs[min_freq]->pop();
230 if(node){
231 // cout << "evict (" << node->key << ", " << node->value << ")" << endl;
232 nodes.erase(node->key);
233 }
234 }
235
236 DListNode* node = new DListNode(key, value);
237 nodes[key] = node;
238 if(freqs.find(1) == freqs.end()) freqs[1] = new DList();
239 freqs[1]->prepend(node);
240 min_freq = 1;
241 }
242 }
243};
244
245/**
246 * Your LFUCache object will be instantiated and called as such:
247 * LFUCache* obj = new LFUCache(capacity);
248 * int param_1 = obj->get(key);
249 * obj->put(key,value);
250 */Cost
Complexity
Time
time = 0;
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.