LFU Cache
LFU Cache is a hard design data structures problem solved with the linked lists pattern.
The best approach, optimal (count buckets + minimum count), runs in O(1) average per operation time and O(capacity) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan for the victim) up.
Problem
Build a class LFUCache that stores key–value pairs and can hold at most capacity of them. LFUCache(int capacity) creates an empty cache.
get(int key) returns the value stored for key, or -1 if it is absent. put(int key, int value) stores the value, overwriting it if the key is already present. Every successful get and every put counts as one use of that key; a key that has just been inserted has been used once.
When a put brings a new key into a cache that is already full, the cache first evicts the key with the fewest uses. If several keys tie, it evicts the one among them whose last use is the oldest. Both operations must run in O(1) average time.
Examples
Example 1
- Input
LFUCache(2), put(5, 50), put(8, 80), get(5), put(3, 30), get(8), get(3), get(5)- Output
50, -1, 30, 50- Why
- After get(5), key 5 has been used twice and key 8 once, so adding key 3 to the full cache evicts key 8.
Example 2
- Input
LFUCache(2), put(1, 10), put(2, 20), get(1), get(2), put(4, 40), get(1), get(2), get(4)- Output
10, 20, -1, 20, 40- Why
- Keys 1 and 2 are both used twice; key 1 was touched longer ago, so the tie is broken by evicting it.
Example 3
- Input
LFUCache(1), put(6, 1), put(6, 2), get(6), put(7, 3), get(6), get(7)- Output
2, -1, 3- Why
- Overwriting key 6 counts as a use but frees no space; with room for one entry, key 7 pushes key 6 out.
Constraints
1 <= capacity <= 10^40 <= key <= 10^50 <= value <= 10^9- At most
2 * 10^5calls togetandputin total. - Both
getandputmust run in O(1) average time.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan for the victim) | O(capacity) per put that evicts, O(1) otherwise | O(capacity) |
| Optimal (count buckets + minimum count) | O(1) average per operation | O(capacity) |
1Brute force (scan for the victim)
O(capacity) per put that evicts, O(1) otherwiseChoosing a victim looks at every stored entry.O(capacity)Each of at most `capacity` keys stores three numbers.Store each key with its value, its use count and the tick of its last use. Lookups are direct, but when the cache is full you scan every entry and pick the one with the smallest count, breaking ties by the oldest tick.
- Keep a global counter
tickthat grows on every access. - get(key): if missing return -1; otherwise add 1 to its count, set its last use to the next tick and return the value.
- put(key, value) on an existing key: update the value, add 1 to the count and refresh the tick.
- put on a new key when full: scan all entries for the smallest (count, lastUse) pair and remove that key.
- Insert the new key with count 1 and the next tick.
class LFUCache {
private final int capacity;
private final Map<Integer, int[]> data = new HashMap<>(); // key -> {value, count, lastUse}
private int tick = 0;
public LFUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
int[] e = data.get(key);
if (e == null) return -1;
e[1]++;
e[2] = ++tick;
return e[0];
}
public void put(int key, int value) {
int[] e = data.get(key);
if (e != null) {
e[0] = value;
e[1]++;
e[2] = ++tick;
return;
}
if (data.size() == capacity) {
int victim = -1;
int[] best = null;
for (Map.Entry<Integer, int[]> en : data.entrySet()) {
int[] v = en.getValue();
if (best == null || v[1] < best[1] || (v[1] == best[1] && v[2] < best[2])) {
best = v;
victim = en.getKey();
}
}
data.remove(victim);
}
data.put(key, new int[] { value, 1, ++tick });
}
}class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = {} # key -> [value, count, lastUse]
self.tick = 0
def get(self, key: int) -> int:
e = self.data.get(key)
if e is None:
return -1
self.tick += 1
e[1] += 1
e[2] = self.tick
return e[0]
def put(self, key: int, value: int) -> None:
self.tick += 1
e = self.data.get(key)
if e is not None:
e[0] = value
e[1] += 1
e[2] = self.tick
return
if len(self.data) == self.capacity:
victim = min(self.data, key=lambda k: (self.data[k][1], self.data[k][2]))
del self.data[victim]
self.data[key] = [value, 1, self.tick]class LFUCache {
int capacity;
int tick = 0;
unordered_map<int, array<int, 3>> data; // key -> {value, count, lastUse}
public:
LFUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = data.find(key);
if (it == data.end()) return -1;
it->second[1]++;
it->second[2] = ++tick;
return it->second[0];
}
void put(int key, int value) {
auto it = data.find(key);
if (it != data.end()) {
it->second[0] = value;
it->second[1]++;
it->second[2] = ++tick;
return;
}
if ((int)data.size() == capacity) {
auto best = data.begin();
for (auto jt = data.begin(); jt != data.end(); ++jt) {
if (jt->second[1] < best->second[1] ||
(jt->second[1] == best->second[1] && jt->second[2] < best->second[2])) {
best = jt;
}
}
data.erase(best);
}
data[key] = {value, 1, ++tick};
}
};class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.data = new Map(); // key -> [value, count, lastUse]
this.tick = 0;
}
get(key) {
const e = this.data.get(key);
if (e === undefined) return -1;
e[1]++;
e[2] = ++this.tick;
return e[0];
}
put(key, value) {
const e = this.data.get(key);
if (e !== undefined) {
e[0] = value;
e[1]++;
e[2] = ++this.tick;
return;
}
if (this.data.size === this.capacity) {
let victim = -1;
let best = null;
for (const [k, v] of this.data) {
if (best === null || v[1] < best[1] || (v[1] === best[1] && v[2] < best[2])) {
best = v;
victim = k;
}
}
this.data.delete(victim);
}
this.data.set(key, [value, 1, ++this.tick]);
}
}2Optimal (count buckets + minimum count)
O(1) average per operationEvery step is a hash lookup or an insertion/removal in an insertion-ordered hash set.O(capacity)Each stored key appears once in the maps and once in one bucket.Put every key into a bucket for its use count. Each bucket is an insertion-ordered set, so its first key is the least recently used one with that count. Track minCount, the smallest count that has a non-empty bucket: the victim is always the first key of bucket minCount. Touching a key moves it from bucket c to the end of bucket c + 1, and only that move can raise minCount, by exactly one.
- Keep
vals(key -> value),counts(key -> count),buckets(count -> ordered set of keys) andminCount. - touch(key): remove it from bucket c; if that bucket was
minCountand is now empty, raiseminCountto c + 1; append the key to bucket c + 1. - get(key): missing -> -1; otherwise touch it and return its value.
- put on an existing key: update the value and touch it.
- put on a new key: if full, remove the first key of bucket
minCountfrom everything; then store the key with count 1, append it to bucket 1 and setminCountto 1.
class LFUCache {
private final int capacity;
private final Map<Integer, Integer> vals = new HashMap<>();
private final Map<Integer, Integer> counts = new HashMap<>();
private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>();
private int minCount = 0;
public LFUCache(int capacity) {
this.capacity = capacity;
}
private void touch(int key) {
int c = counts.get(key);
LinkedHashSet<Integer> b = buckets.get(c);
b.remove(key);
if (b.isEmpty()) {
buckets.remove(c);
if (minCount == c) minCount = c + 1;
}
counts.put(key, c + 1);
buckets.computeIfAbsent(c + 1, x -> new LinkedHashSet<>()).add(key);
}
public int get(int key) {
if (!vals.containsKey(key)) return -1;
touch(key);
return vals.get(key);
}
public void put(int key, int value) {
if (vals.containsKey(key)) {
vals.put(key, value);
touch(key);
return;
}
if (vals.size() == capacity) {
LinkedHashSet<Integer> b = buckets.get(minCount);
int victim = b.iterator().next();
b.remove(victim);
if (b.isEmpty()) buckets.remove(minCount);
vals.remove(victim);
counts.remove(victim);
}
vals.put(key, value);
counts.put(key, 1);
buckets.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key);
minCount = 1;
}
}from collections import OrderedDict
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.vals = {}
self.counts = {}
self.buckets = {} # count -> OrderedDict of keys (oldest first)
self.min_count = 0
def _touch(self, key: int) -> None:
c = self.counts[key]
b = self.buckets[c]
del b[key]
if not b:
del self.buckets[c]
if self.min_count == c:
self.min_count = c + 1
self.counts[key] = c + 1
self.buckets.setdefault(c + 1, OrderedDict())[key] = None
def get(self, key: int) -> int:
if key not in self.vals:
return -1
self._touch(key)
return self.vals[key]
def put(self, key: int, value: int) -> None:
if key in self.vals:
self.vals[key] = value
self._touch(key)
return
if len(self.vals) == self.capacity:
b = self.buckets[self.min_count]
victim, _ = b.popitem(last=False)
if not b:
del self.buckets[self.min_count]
del self.vals[victim]
del self.counts[victim]
self.vals[key] = value
self.counts[key] = 1
self.buckets.setdefault(1, OrderedDict())[key] = None
self.min_count = 1class LFUCache {
int capacity;
int minCount = 0;
unordered_map<int, int> vals, counts;
unordered_map<int, list<int>> buckets; // count -> keys, oldest first
unordered_map<int, list<int>::iterator> where; // key -> position in its bucket
void touch(int key) {
int c = counts[key];
list<int>& b = buckets[c];
b.erase(where[key]);
if (b.empty()) {
buckets.erase(c);
if (minCount == c) minCount = c + 1;
}
counts[key] = c + 1;
list<int>& nb = buckets[c + 1];
nb.push_back(key);
where[key] = prev(nb.end());
}
public:
LFUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = vals.find(key);
if (it == vals.end()) return -1;
touch(key);
return it->second;
}
void put(int key, int value) {
auto it = vals.find(key);
if (it != vals.end()) {
it->second = value;
touch(key);
return;
}
if ((int)vals.size() == capacity) {
list<int>& b = buckets[minCount];
int victim = b.front();
b.pop_front();
if (b.empty()) buckets.erase(minCount);
vals.erase(victim);
counts.erase(victim);
where.erase(victim);
}
vals[key] = value;
counts[key] = 1;
list<int>& b1 = buckets[1];
b1.push_back(key);
where[key] = prev(b1.end());
minCount = 1;
}
};class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.vals = new Map();
this.counts = new Map();
this.buckets = new Map(); // count -> Set of keys, oldest first
this.minCount = 0;
}
touch(key) {
const c = this.counts.get(key);
const b = this.buckets.get(c);
b.delete(key);
if (b.size === 0) {
this.buckets.delete(c);
if (this.minCount === c) this.minCount = c + 1;
}
this.counts.set(key, c + 1);
if (!this.buckets.has(c + 1)) this.buckets.set(c + 1, new Set());
this.buckets.get(c + 1).add(key);
}
get(key) {
if (!this.vals.has(key)) return -1;
this.touch(key);
return this.vals.get(key);
}
put(key, value) {
if (this.vals.has(key)) {
this.vals.set(key, value);
this.touch(key);
return;
}
if (this.vals.size === this.capacity) {
const b = this.buckets.get(this.minCount);
const victim = b.values().next().value;
b.delete(victim);
if (b.size === 0) this.buckets.delete(this.minCount);
this.vals.delete(victim);
this.counts.delete(victim);
}
this.vals.set(key, value);
this.counts.set(key, 1);
if (!this.buckets.has(1)) this.buckets.set(1, new Set());
this.buckets.get(1).add(key);
this.minCount = 1;
}
}Edge cases to test
- Capacity 1: every new key evicts the only entry, whatever its count
- Several keys share the lowest use count: the least recently used of them goes
puton an existing key updates the value and raises its count, but never evicts- A newly inserted key starts with count 1, so it is usually the next one evicted
geton a missing key returns -1 and changes nothing
Hints
Hint 1
Each key needs a use count. When you must evict, you want the smallest count, and among those the oldest. What tells you the oldest quickly?
Hint 2
Group keys by their count. Inside one group, keep them in the order they were last touched, like a small LRU list.
Hint 3
Keep a map key -> (value, count), a map count -> ordered set of keys, and the current minimum count. A new key always resets the minimum to 1; a touched key only raises the minimum when it leaves the minimum group and that group becomes empty.
FAQ
What is the best time complexity for LFU Cache?
Optimal (count buckets + minimum count) runs in O(1) average per operation time and O(capacity) extra space. Every step is a hash lookup or an insertion/removal in an insertion-ordered hash set.
Which pattern does LFU Cache use?
It is a design data structures problem that uses the linked lists pattern. Other problems with the same pattern: Design Linked List, Design Front Middle Back Queue, LRU Cache.
Is there a brute force solution for LFU Cache?
Yes. Brute force (scan for the victim) takes O(capacity) per put that evicts, O(1) otherwise time and O(capacity) space. Store each key with its value, its use count and the tick of its last use.
Which edge cases should I test for LFU Cache?
Capacity 1: every new key evicts the only entry, whatever its count; Several keys share the lowest use count: the least recently used of them goes; put on an existing key updates the value and raises its count, but never evicts; A newly inserted key starts with count 1, so it is usually the next one evicted; get on a missing key returns -1 and changes nothing.