How do you approach LFU Cache?

Maintain a key→(value, freq) map and a freq→ordered-set-of-keys map (a doubly linked list of keys per frequency bucket).

What is the time complexity of LFU Cache?

Time complexity: O(1) per op. Space complexity: O(capacity).

What are common mistakes on LFU Cache?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

LFU Cache

HardObject-Oriented Design

Description

Design and implement a data structure for a **Least Frequently Used (LFU) cache**. - `get(key)`: Returns the value if `key` exists, else `-1`. Each access (get or put-existing) increments the key's frequency by 1. - `put(key, value)`: Insert or update. If at capacity, evict the **least frequently used** key. Tie-break by the **least recently used** among keys with the lowest frequency. Both operations must run in **O(1) average time**. **For the auto-grader:** implement `lfuCacheOps(capacity, operations)` returning the result of each call in order: - `["put", key, value]` → `null` / `None` - `["get", key]` → value or `-1`

Example 1

Input: capacity = 2, operations = [["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: [null,null,1,null,-1,3,null,-1,3,4]

Explanation: After get(1), key 1 has freq 2, key 2 has freq 1. put(3,3) evicts key 2 (lowest freq). put(4,4) evicts key 1 (key 1 has freq 2, key 3 has freq 2, but key 1 was used less recently).

Constraints

- 0 <= capacity <= 10^4 - 0 <= key, value <= 10^9 - At most 2 * 10^5 calls.

LFU Cache: approach, complexity and pitfalls

A hard design problem, graded against 4 test cases (1 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

More Designproblems →

If you are stuck

Show the 3-step hint ladder

Maintain a key→(value, freq) map and a freq→ordered-set-of-keys map (a doubly linked list of keys per frequency bucket).
Track minFreq. On eviction, remove the LRU key from the minFreq bucket.
On a get/put-existing, increment freq: remove from old bucket, append to new bucket, update minFreq if old bucket emptied.

The optimal approach

Show the approach: Two Maps + Per-Frequency Doubly Linked Lists

Maintain three structures:

1. `keyToVal`: key → value

2. `keyToFreq`: key → frequency count

3. `freqToList`: freq → ordered list of keys (most-recent at the head, LRU at the tail) - an OrderedDict in Python or a hash-map+doubly-linked-list pair in JS.

Plus a single integer `minFreq`.

get(key): read keyToVal; if hit, increment frequency:

- Remove key from `freqToList[oldFreq]`. If that list is empty and `oldFreq == minFreq`, increment `minFreq`.

- Append key to `freqToList[oldFreq + 1]`.

- `keyToFreq[key] = oldFreq + 1`.

put(key, val):

- If `capacity == 0`, no-op.

- If key exists: update value, then bump frequency exactly like get.

- Else: if at capacity, evict the LRU key from `freqToList[minFreq]`. Insert the new key at frequency 1, then `minFreq = 1`.

The "LRU within freq" tie-break is what an OrderedDict gives you for free.

Time: O(1) per op
Space: O(capacity)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.