Log inSign up
hardLeetCodeNot Started

LFU Cache

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

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): Update 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 should be invalidated.

To determine the least frequently used key, a use counter is maintained for each key. The use counter is incremented each time a get or put operation is called on the key.

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

Example 1 · 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) = use counter of key x // set([1, 1], cnt=1), set([2, 2], cnt=1) 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(1)=2, cnt(2)=1 lfu.put(3, 3); // 2 is evicted because cnt(2)=1 is lowest. cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // returns -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 was used least recently. 1 is evicted. cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // return -1 (not found) lfu.get(3); // return 3 lfu.get(4); // return 4

Constraints:

  • 1 <= capacity <= 104
  • 0 <= key <= 105
  • 0 <= value <= 109
  • At most 2 * 105 calls will be made to get and put.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for LFU Cache.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • LFU Cache
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Basic prototyping when capacity is tiny (C <= 20).
  • BETTER: When simplicity of balanced tree libraries is preferred over custom linked lists.
  • OPTIMAL: Optimal standard for production-grade LFU caches requiring guaranteed O(1) performance.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Array with Linear Search for Eviction

Intuition

Store all entries in an array where each record holds (key, value, freq, lastAccessTime). - get(key): Scan linearly for key. If found, increment freq, update lastAccessTime, and return value. Otherwise return -1. - put(key, value): If key exists, update value, increment freq, and update time. If new and at capacity, scan all entries to find the entry with the minimum frequency; break ties using oldest lastAccessTime. Overwrite or remove that entry. Because every operation scans up to C entries, this requires O(C) time per operation.

When to apply: Basic prototyping when capacity is tiny (C <= 20).

Algorithm

  1. Step 1: Store entries in an array with fields key, value, frequency, timestamp.
  2. Step 2: On get, search array. If found, increment freq and timestamp, return value; else return -1.
  3. Step 3: On put, if key exists, update value and increment freq.
  4. Step 4: If key is new and at capacity, scan to find min freq (and min timestamp for ties), remove it.
  5. Step 5: Append new entry with freq = 1 and current timestamp.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <climits>
4
5struct Node {
6 int key, value, freq, time;
7};
8
9class LFUCacheBrute {
10 int capacity;
11 int timer = 0;
12 std::vector<Node> cache;
13public:
14 LFUCacheBrute(int cap) : capacity(cap) {}
15
16 int get(int key) {
17 for (auto& node : cache) {
18 if (node.key == key) {
19 node.freq++;
20 node.time = ++timer;
21 return node.value;
22 }
23 }
24 return -1;
25 }
26
27 void put(int key, int value) {
28 if (capacity <= 0) return;
29 for (auto& node : cache) {
30 if (node.key == key) {
31 node.value = value;
32 node.freq++;
33 node.time = ++timer;
34 return;
35 }
36 }
37 if ((int)cache.size() >= capacity) {
38 int minIdx = 0;
39 for (int i = 1; i < (int)cache.size(); ++i) {
40 if (cache[i].freq < cache[minIdx].freq ||
41 (cache[i].freq == cache[minIdx].freq && cache[i].time < cache[minIdx].time)) {
42 minIdx = i;
43 }
44 }
45 cache.erase(cache.begin() + minIdx);
46 }
47 cache.push_back({key, value, 1, ++timer});
48 }
49};
50
51int main() {
52 LFUCacheBrute lfu(2);
53 lfu.put(1, 1);
54 lfu.put(2, 2);
55 std::cout << lfu.get(1) << std::endl;
56 lfu.put(3, 3);
57 std::cout << lfu.get(2) << std::endl;
58 std::cout << lfu.get(3) << std::endl;
59 lfu.put(4, 4);
60 std::cout << lfu.get(1) << std::endl;
61 std::cout << lfu.get(3) << std::endl;
62 std::cout << lfu.get(4) << std::endl;
63 return 0;
64}

Time & Space Complexity

  • Time complexity: O(C) per get and put where C is cache capacity
  • Space complexity: O(C) space for storing cache items

2. Hash Map + Self-Balancing BST / Sorted Set

Intuition

Use a hash map keyToNode for O(1) key lookups, and a balanced search tree (such as C++ std::set or Java TreeSet) to keep nodes ordered by (freq, time, key). - On get(key): 1. Retrieve node from map in O(1). 2. Remove node from the BST in O(log C). 3. Increment node's freq and update time. 4. Re-insert node into BST in O(log C). - On put(key, value): 1. If key exists, update value and update frequency in BST as in get (O(log C)). 2. If new and at capacity, the BST root/begin iterator points directly to the minimum frequency (and oldest timestamp) node. Erase it from both BST and hash map in O(log C). 3. Insert the new node with freq = 1 into both BST and hash map in O(log C). Every operation executes in O(log C) time.

When to apply: When simplicity of balanced tree libraries is preferred over custom linked lists.

Algorithm

  1. Step 1: Maintain hash map keyToNode and a balanced BST ordered by (freq, time).
  2. Step 2: On get, locate node in map. If missing, return -1. Otherwise erase from BST, increment freq and time, and re-insert into BST.
  3. Step 3: On put of existing key, update value, erase from BST, increment freq, re-insert into BST.
  4. Step 4: On put of new key at capacity, erase BST.begin() from both BST and map.
  5. Step 5: Insert new node into map and BST.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3#include <set>
4
5struct CacheNode {
6 int key, value, freq, time;
7 bool operator<(const CacheNode& o) const {
8 if (freq != o.freq) return freq < o.freq;
9 return time < o.time;
10 }
11};
12
13class LFUCacheBST {
14 int capacity;
15 int timer = 0;
16 std::unordered_map<int, CacheNode> keyMap;
17 std::set<CacheNode> bst;
18public:
19 LFUCacheBST(int cap) : capacity(cap) {}
20
21 int get(int key) {
22 auto it = keyMap.find(key);
23 if (it == keyMap.end()) return -1;
24 CacheNode node = it->second;
25 bst.erase(node);
26 node.freq++;
27 node.time = ++timer;
28 bst.insert(node);
29 it->second = node;
30 return node.value;
31 }
32
33 void put(int key, int value) {
34 if (capacity <= 0) return;
35 auto it = keyMap.find(key);
36 if (it != keyMap.end()) {
37 CacheNode node = it->second;
38 bst.erase(node);
39 node.value = value;
40 node.freq++;
41 node.time = ++timer;
42 bst.insert(node);
43 it->second = node;
44 return;
45 }
46 if ((int)keyMap.size() >= capacity) {
47 auto victim = bst.begin();
48 keyMap.erase(victim->key);
49 bst.erase(victim);
50 }
51 CacheNode newNode = {key, value, 1, ++timer};
52 keyMap[key] = newNode;
53 bst.insert(newNode);
54 }
55};
56
57int main() {
58 LFUCacheBST lfu(2);
59 lfu.put(1, 1);
60 lfu.put(2, 2);
61 std::cout << lfu.get(1) << std::endl;
62 lfu.put(3, 3);
63 std::cout << lfu.get(2) << std::endl;
64 std::cout << lfu.get(3) << std::endl;
65 lfu.put(4, 4);
66 std::cout << lfu.get(1) << std::endl;
67 std::cout << lfu.get(3) << std::endl;
68 std::cout << lfu.get(4) << std::endl;
69 return 0;
70}

Time & Space Complexity

  • Time complexity: O(log C) per get and put where C is capacity
  • Space complexity: O(C) space for map and balanced BST

3. Hash Map + Doubly Linked Lists per Frequency (O(1) All Ops)

Intuition

To achieve strict O(1) time for both operations: 1. Maintain keyTable: key -> Node(key, value, freq). 2. Maintain freqTable: freq -> DoublyLinkedList of nodes having this exact frequency. Within each DoublyLinkedList, nodes are arranged in LRU order (most recently accessed at the head, least recently at the tail). 3. Maintain an integer minFreq: - When a node with frequency f is accessed, remove it from freqTable[f] and insert it into freqTable[f + 1]. - If freqTable[f] becomes empty and f == \text{minFreq}, increment \text{minFreq} = \text{minFreq} + 1. 4. On eviction (when capacity exceeded): - The eviction target is the least recently used node in the list of frequency \text{minFreq} (i.e., freqTable[minFreq].tail.prev). - Evict it from the list and delete it from keyTable in O(1). 5. On inserting a brand new key: - Set node frequency to 1, insert into freqTable[1], and reset \text{minFreq} = 1. Every insertion, lookup, frequency increment, and eviction runs in pure O(1) constant time.

When to apply: Optimal standard for production-grade LFU caches requiring guaranteed O(1) performance.

Algorithm

  1. Step 1: Define Node with key, value, freq, prev, and next pointers, and a DoublyLinkedList helper.
  2. Step 2: On get(key), if key absent, return -1. Otherwise update node frequency via helper updateFreq(node) and return node.value.
  3. Step 3: On put(key, value), if key exists, update value and call updateFreq(node).
  4. Step 4: If key is new and size == capacity, evict the tail of freqTable[minFreq] from both list and keyTable.
  5. Step 5: Insert new node into keyTable and freqTable[1], and reset minFreq = 1.

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
put(1, 1), put(2, 2): Insert keys 1 and 2 with frequency 1
Visual state
Values and pointers at this exact step
pointers
S
1
2
0
1
↑ minFreq
Check / comparison
Capacity 2 reached
Decision / next transition
keyMap has 1 and 2
Why this step matters

put(1, 1), put(2, 2): Insert keys 1 and 2 with frequency 1. minFreq = 1. freqMap[1] contains [2, 1].

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3
4struct Node {
5 int key, val, freq;
6 Node *prev, *next;
7 Node(int k, int v) : key(k), val(v), freq(1), prev(nullptr), next(nullptr) {}
8};
9
10struct DList {
11 Node *head, *tail;
12 int size;
13 DList() : size(0) {
14 head = new Node(0, 0);
15 tail = new Node(0, 0);
16 head->next = tail;
17 tail->prev = head;
18 }
19 void addFront(Node* node) {
20 node->next = head->next;
21 node->prev = head;
22 head->next->prev = node;
23 head->next = node;
24 size++;
25 }
26 void remove(Node* node) {
27 node->prev->next = node->next;
28 node->next->prev = node->prev;
29 size--;
30 }
31 Node* removeTail() {
32 if (size == 0) return nullptr;
33 Node* node = tail->prev;
34 remove(node);
35 return node;
36 }
37};
38
39class LFUCache {
40 int capacity, minFreq;
41 std::unordered_map<int, Node*> keyMap;
42 std::unordered_map<int, DList*> freqMap;
43
44 void updateFreq(Node* node) {
45 int f = node->freq;
46 freqMap[f]->remove(node);
47 if (freqMap[f]->size == 0 && f == minFreq) {
48 minFreq++;
49 }
50 node->freq++;
51 if (!freqMap.count(node->freq)) {
52 freqMap[node->freq] = new DList();
53 }
54 freqMap[node->freq]->addFront(node);
55 }
56
57public:
58 LFUCache(int cap) : capacity(cap), minFreq(0) {}
59
60 int get(int key) {
61 auto it = keyMap.find(key);
62 if (it == keyMap.end()) return -1;
63 updateFreq(it->second);
64 return it->second->val;
65 }
66
67 void put(int key, int value) {
68 if (capacity <= 0) return;
69 auto it = keyMap.find(key);
70 if (it != keyMap.end()) {
71 it->second->val = value;
72 updateFreq(it->second);
73 return;
74 }
75 if ((int)keyMap.size() >= capacity) {
76 Node* victim = freqMap[minFreq]->removeTail();
77 keyMap.erase(victim->key);
78 delete victim;
79 }
80 Node* newNode = new Node(key, value);
81 keyMap[key] = newNode;
82 minFreq = 1;
83 if (!freqMap.count(1)) freqMap[1] = new DList();
84 freqMap[1]->addFront(newNode);
85 }
86};
87
88int main() {
89 LFUCache lfu(2);
90 lfu.put(1, 1);
91 lfu.put(2, 2);
92 std::cout << lfu.get(1) << std::endl;
93 lfu.put(3, 3);
94 std::cout << lfu.get(2) << std::endl;
95 std::cout << lfu.get(3) << std::endl;
96 lfu.put(4, 4);
97 std::cout << lfu.get(1) << std::endl;
98 std::cout << lfu.get(3) << std::endl;
99 std::cout << lfu.get(4) << std::endl;
100 return 0;
101}

Time & Space Complexity

  • Time complexity: O(1) for both get and put operations
  • Space complexity: O(capacity) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array with Linear Search for EvictionO(C) per get and put where C is cache capacityO(C) space for storing cache itemsStore items as structs in a list. Linearly search on get/put and scan for minimum frequency and oldest timestamp upon eviction.O(C) per get and put where C is cache capacity
2.Hash Map + Self-Balancing BST / Sorted SetO(log C) per get and put where C is capacityO(C) space for map and balanced BSTMaintain key lookup via hash map and maintain order of (frequency, timestamp, key) using a balanced BST (std::set / TreeSet).O(log C) per get and put where C is capacity
3.Hash Map + Doubly Linked Lists per Frequency (O(1) All Ops)OptimalO(1) for both get and put operationsO(capacity) auxiliary spaceMap keys to nodes, and map each frequency to a doubly linked list of nodes. Maintain minFreq pointer to achieve strict O(1) get and put.O(1) for both get and put operations

Common Pitfalls & Crucial Edge Cases

Using a Min-Heap (Priority Queue)

Heap operations take O(log N) time, which fails the strict O(1) time complexity requirement.

Forgetting to reset `minFreq = 1` on new key insertion

A newly inserted key always has frequency 1, so minFreq must become 1.

Capacity 0 crash

Forgetting the if (capacity <= 0) return; guard causes null pointer exceptions during eviction.

Crucial Edge Cases to Validate:

  • capacity == 0 — Any put call cannot store items; immediately return without inserting.
  • Updating an existing key at maximum capacity — Should NOT evict another key; simply updates the value and increments frequency.
  • Inserting a new key at maximum capacity — Evicts the least recently used node in freqMap[minFreq], then inserts new node with frequency 1 and sets minFreq = 1.
  • All keys have equal frequency — Behaves identically to an LRU cache.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Acknowledge that LFU is one of the most technically demanding cache design problems in software engineering interviews.
  2. Draw the architectural diagram: keyMap: Key -> Node, freqMap: Freq -> DoublyLinkedList, minFreq: int.
  3. Explain how the Doubly Linked List cleanly enforces LRU tie-breaking within each frequency tier.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What data structures allow LFU Cache to achieve O(1) for both get and put?

2.When two keys share the exact same minimum frequency, which one is evicted?

3.How is minFreq updated when an existing key's frequency increments from f to f + 1?

Back to DSA Sheet