LFU Cache
Hard · Linked List · Explanation and code example
Doubly Linked List
How it works
To achieve O(1) operations, we need fast access to a key's current node and to the least recently used node inside each frequency group. We use a hash map from frequency to a doubly linked list of cache nodes, and a separate key-to-node map for direct access. Each linked list maintains recency order within one frequency bucket, so the head is the eviction candidate for ties. We also track the current minimum frequency to quickly find which list to evict from.
Steps
- Maintain a
nodeMap(or equivalent key-to-node lookup) and alistMap(frequency to doubly linked list of nodes). - Track
lfuCount, the current minimum frequency in the cache. - For
get(key): if the key exists, move it from its current frequency list to the next frequency list, update the frequency, and adjustlfuCountif needed. - For
put(key, value): if the key exists, update its value and treat it like agetoperation. If inserting a new key and at capacity, pop the leftmost (oldest) element from thelfuCountlist. - Insert the new key into frequency-1 list and set
lfuCountto1.
Complexity
- Time complexity:
O(1)time for initialization.O(1)time for eachget()andput()function calls.
- Space complexity:
O(n)
Things to watch for
Not Resetting Minimum Frequency on New Insertions
When inserting a new key, the minimum frequency tracker must reflect that the new key starts at frequency 1. Failing to update lfuCount causes subsequent evictions to look in the wrong frequency bucket, potentially evicting the wrong item or causing errors.
Not Incrementing Frequency on Both Get and Put
Both get() and put() (when updating an existing key) should increment the frequency. A common mistake is only incrementing on get(), which causes keys that are repeatedly updated but never retrieved to have artificially low frequencies and get evicted prematurely.
Incorrect LRU Tie-Breaking Within Same Frequency
When multiple keys share the same minimum frequency, the least recently used among them should be evicted. This requires maintaining insertion order within each frequency bucket. Using a regular set or unordered structure loses this ordering and leads to incorrect evictions.
Not Handling Zero Capacity Edge Case
When the cache capacity is 0, all put() operations should be no-ops since nothing can be stored. Forgetting this check causes attempts to evict from an empty cache, leading to errors or incorrect behavior.
Failing to Move Nodes Between Frequency Lists
When a key's frequency increases, its node must be removed from the current frequency list and added to the next one. Forgetting to remove it from the old list causes the same entry to appear in multiple frequency buckets, corrupting the data structure and causing incorrect evictions.
Python code example
from collections import defaultdict
class ListNode:
def __init__(self, key, val):
self.key = key
self.val = val
self.freq = 1
self.prev = None
self.next = None
class LinkedList:
def __init__(self):
self.left = ListNode(0, 0)
self.right = ListNode(0, 0)
self.left.next = self.right
self.right.prev = self.left
self.size = 0
def length(self):
return self.size
def pushRight(self, node):
prev = self.right.prev
prev.next = node
node.prev = prev
node.next = self.right
self.right.prev = node
self.size += 1
def pop(self, node):
prev, next = node.prev, node.next
prev.next = next
next.prev = prev
node.prev = None
node.next = None
self.size -= 1
def popLeft(self):
if self.length() == 0:
return None
node = self.left.next
self.pop(node)
return node
class LFUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.lfuCnt = 0
self.nodeMap = {} # Map key -> node
# Map frequency -> linkedlist of nodes
self.listMap = defaultdict(LinkedList)
def counter(self, node):
cnt = node.freq
self.listMap[cnt].pop(node)
if cnt == self.lfuCnt and self.listMap[cnt].length() == 0:
self.lfuCnt += 1
node.freq += 1
self.listMap[node.freq].pushRight(node)
def get(self, key: int) -> int:
if key not in self.nodeMap:
return -1
node = self.nodeMap[key]
self.counter(node)
return node.val
def put(self, key: int, value: int) -> None:
if self.cap == 0:
return
if key in self.nodeMap:
node = self.nodeMap[key]
node.val = value
self.counter(node)
return
if len(self.nodeMap) == self.cap:
node = self.listMap[self.lfuCnt].popLeft()
self.nodeMap.pop(node.key)
node = ListNode(key, value)
self.nodeMap[key] = node
self.listMap[1].pushRight(node)
self.lfuCnt = 1
C++ code example
class LFUCache {
struct ListNode {
int key;
int val;
int freq;
ListNode* prev;
ListNode* next;
ListNode(int key, int val) : key(key), val(val), freq(1), prev(nullptr), next(nullptr) {}
};
struct LinkedList {
ListNode* left;
ListNode* right;
int size;
LinkedList() {
left = new ListNode(0, 0);
right = new ListNode(0, 0);
left->next = right;
right->prev = left;
size = 0;
}
~LinkedList() {
delete left;
delete right;
}
int length() {
return size;
}
void pushRight(ListNode* node) {
ListNode* prev = right->prev;
prev->next = node;
node->prev = prev;
node->next = right;
right->prev = node;
size++;
}
void pop(ListNode* node) {
ListNode* prev = node->prev;
ListNode* next = node->next;
prev->next = next;
next->prev = prev;
node->prev = nullptr;
node->next = nullptr;
size--;
}
ListNode* popLeft() {
ListNode* node = left->next;
pop(node);
return node;
}
};
int capacity;
int lfuCount;
unordered_map<int, ListNode*> nodeMap; // Map key -> node
unordered_map<int, LinkedList*> listMap; // Map frequency -> linked list
void counter(ListNode* node) {
int count = node->freq;
listMap[count]->pop(node);
if (count == lfuCount && listMap[count]->length() == 0) {
lfuCount++;
}
node->freq++;
if (!listMap.count(node->freq)) {
listMap[node->freq] = new LinkedList();
}
listMap[node->freq]->pushRight(node);
}
public:
LFUCache(int capacity) : capacity(capacity), lfuCount(0) {}
~LFUCache() {
for (auto& pair : nodeMap) {
delete pair.second;
}
for (auto& pair : listMap) {
delete pair.second;
}
}
int get(int key) {
if (nodeMap.find(key) == nodeMap.end()) {
return -1;
}
ListNode* node = nodeMap[key];
counter(node);
return node->val;
}
void put(int key, int value) {
if (capacity == 0) {
return;
}
if (nodeMap.find(key) != nodeMap.end()) {
ListNode* node = nodeMap[key];
node->val = value;
counter(node);
return;
}
if (nodeMap.size() == capacity) {
ListNode* toRemove = listMap[lfuCount]->popLeft();
nodeMap.erase(toRemove->key);
delete toRemove;
}
ListNode* node = new ListNode(key, value);
nodeMap[key] = node;
if (!listMap.count(1)) {
listMap[1] = new LinkedList();
}
listMap[1]->pushRight(node);
lfuCount = 1;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.