LFU Cache

Hard

Problem

Design a Least Frequently Used cache with a fixed capacity. get(key) returns the value, or −1 if absent. put(key, value) inserts or updates a key. When the cache is full, evict the key with the lowest use count; break ties by evicting the least recently used of them. Every get or put on a key increases its count. Both operations must be O(1).

Example 1

Input:  capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), get(3), put(4,4), get(1), get(3), get(4)
Output: 1, -1, 3, -1, 3, 4

Test cases

Case 1

Input:    new LFUCache(2)
.put(1, 1)
.put(2, 2)
.get(1)
.put(3, 3)
.get(2)
.get(3)
.put(4, 4)
.get(1)
.get(3)
.get(4)
Expected: [null,null,1,null,-1,3,null,-1,3,4]

Case 2

Input:    new LFUCache(0)
.put(0, 0)
.get(0)
Expected: [null,-1]

Case 3

Input:    new LFUCache(2)
.put(1, 1)
.put(2, 2)
.put(3, 3)
.get(1)
.get(2)
.get(3)
Expected: [null,null,null,-1,2,3]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Frequency buckets of insertion-ordered sets

Time O(1) per operationSpace O(capacity)

key → [value, freq]; freq → Set of keys (JS Sets keep insertion order, so the first key is the least recent). Track minFreq; evict the first key of the minFreq bucket. A new key resets minFreq to 1.

class LFUCache {
constructor(capacity) {
this.cap = capacity;
this.vals = new Map(); // key -> [value, freq]
this.buckets = new Map(); // freq -> Set(keys), oldest first
this.minFreq = 0;
}
#touch(key) {
const entry = this.vals.get(key), f = entry[1];
this.buckets.get(f).delete(key);
if (f === this.minFreq && this.buckets.get(f).size === 0) this.minFreq++;
entry[1] = f + 1;
if (!this.buckets.has(f + 1)) this.buckets.set(f + 1, new Set());
this.buckets.get(f + 1).add(key);
}
get(key) {
if (!this.vals.has(key)) return -1;
this.#touch(key);
return this.vals.get(key)[0];
}
put(key, value) {
if (this.cap === 0) return;
if (this.vals.has(key)) {
this.vals.get(key)[0] = value;
this.#touch(key);
return;
}
if (this.vals.size === this.cap) {
const bucket = this.buckets.get(this.minFreq);
const evict = bucket.values().next().value;
bucket.delete(evict);
this.vals.delete(evict);
}
this.vals.set(key, [value, 1]);
if (!this.buckets.has(1)) this.buckets.set(1, new Set());
this.buckets.get(1).add(key);
this.minFreq = 1;
}
}

In other languages the buckets are doubly linked lists; JS Set insertion order gives the same O(1) behaviour.