460. LFU Cache — DSA Atlas

460

HardData Structure DesignHash maps + per-frequency ordered dicts + min-frequency pointerFrequency buckets with per-bucket LRU

LFU Cache

Design an LFU (Least Frequently Used) cache with a given capacity. get(key) returns the value or -1 and counts as a use. put(key, value) inserts or updates; if the cache is full, evict the least frequently used key, breaking ties by evicting the least recently used among those. Both operations must run in O(1) average time. A get or put on a key increases its use frequency by one.

Open official problem prompt ↗

In plain English

Serve a fixed-capacity cache that evicts the least-used key, using recency only to break frequency ties, all in constant time.

Picture it like this

Like a library that shelves books by how often they are borrowed; when space runs out it discards from the least-borrowed shelf, and among equally unpopular books, the one untouched longest.

Example

Input: 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)
Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Why: put(3,3) evicts key 2 (freq 1 vs key1's freq 2); put(4,4) evicts key 1 (keys 1 and 3 both freq 2, key 1 least recently used).

Constraints

0 <= capacity <= 10^40 <= key <= 10^50 <= value <= 10^9At most 2 * 10^5 calls to get and putget and put must be O(1) average time

Pattern lesson

See the pattern, then code

Frequency buckets with per-bucket LRU

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Bucket keys by their exact use frequency, and within each frequency keep insertion/use order (an ordered dict) so the tie-break is the front of the min-frequency bucket; track the current minimum frequency so eviction is O(1).

New words, made simpleKnow these before the algorithm

Frequency bucket: An ordered collection of all keys currently sharing the same use count.
OrderedDict: A dict preserving insertion order, giving O(1) LRU pop from the front.
min_freq: A pointer to the smallest frequency present, so eviction finds the victim bucket instantly.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Scan for min frequency on eviction

Eviction is linear, breaking the O(1) contract.

Store frequencies and scan all keys to find the least frequent when full.

Time O(K) per evictionSpace O(K)

Min-heap keyed by (freq, recency)

Logarithmic and needs stale-entry cleanup - not O(1).

Order candidates in a heap by frequency then recency.

Time O(log K) per operationSpace O(K)

Best choiceFrequency buckets + per-bucket LRU + min_freq

Every access and eviction is constant time with correct freq-then-recency ordering.

Ordered dict per frequency plus a min_freq pointer.

Time O(1) averageSpace O(capacity)

The rule we keep true

Invariant

min_freq always equals the smallest frequency of any key in the cache, and within each frequency bucket keys are ordered oldest-used at the front.

Why this is correct

Reasoning

Each access bumps a key by exactly one frequency, so it moves to an adjacent bucket; min_freq only ever needs to increase when the min bucket empties on an access, and a fresh insert resets it to 1 - so the eviction victim (front of the min_freq bucket) is always the least-frequently, least-recently used key.

The algorithm in three movesSay these aloud before coding

1Store key->value and key->frequency maps

key_freq: 1->2, 3->2, 4->1

2Keep freq -> ordered dict of keys (oldest at the front) and a running min_freq

freq_keys: {1:[4], 2:[1,3]}

3On access, move the key from its freq bucket to the freq+1 bucket, bumping min_freq if its bucket emptied

min_freq=1 -> evict from f1

4On insert at capacity, pop the front (LRU) of the min_freq bucket, then add the new key at frequency 1 and set min_freq = 1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

f1:[4]0

f2:[key1,key3]1

min_freq=12

1 · Readfill cache

2 · Ask-

3 · Update statef1:[1,2], min_freq=1

4 · Resultstored

Key takeaway

Keys grouped by frequency; the min-frequency bucket's front is the next eviction victim.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 1-9State
Value map, frequency map, freq->OrderedDict buckets, and the min_freq pointer.
2
Lines 11-19_touch
Promote a key one frequency up; if its old bucket empties and was the min, advance min_freq.
3
Lines 21-25get
Miss returns -1; a hit touches the key to raise its frequency before returning the value.
4
Lines 27-43put
Update-in-place touches; a full insert evicts the front of the min_freq bucket, then adds the key at frequency 1 and resets min_freq.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

capacity == 0 makes put a no-op and every get returns -1
put on an existing key updates the value and counts as a use
Eviction with ties falls back to least-recently-used within the min bucket
A brand-new key always enters at frequency 1, forcing min_freq back to 1

Common beginner mistakes

Forgetting to reset min_freq to 1 after inserting a new key
Advancing min_freq at the wrong time or when the emptied bucket was not the min
Breaking ties by frequency only and ignoring recency order
Not treating an update as an access and thus miscounting frequency

Check your understanding

After evicting from the min_freq bucket during a new insert, why is it always correct to then set min_freq = 1?

PyPython 3 · solution.py

Optimal

1from collections import defaultdict, OrderedDict23class LFUCache:4    def __init__(self, capacity: int):5        self.cap = capacity6        self.key_val: dict[int, int] = {}7        self.key_freq: dict[int, int] = {}8        self.freq_keys = defaultdict(OrderedDict)9        self.min_freq = 01011    def _touch(self, key: int) -> None:12        f = self.key_freq[key]13        del self.freq_keys[f][key]14        if not self.freq_keys[f]:15            del self.freq_keys[f]16            if self.min_freq == f:17                self.min_freq += 118        self.key_freq[key] = f + 119        self.freq_keys[f + 1][key] = None2021    def get(self, key: int) -> int:22        if key not in self.key_val:23            return -124        self._touch(key)25        return self.key_val[key]2627    def put(self, key: int, value: int) -> None:28        if self.cap <= 0:29            return30        if key in self.key_val:31            self.key_val[key] = value32            self._touch(key)33            return34        if len(self.key_val) >= self.cap:35            evict, _ = self.freq_keys[self.min_freq].popitem(last=False)36            del self.key_val[evict]37            del self.key_freq[evict]38            if not self.freq_keys[self.min_freq]:39                del self.freq_keys[self.min_freq]40        self.key_val[key] = value41        self.key_freq[key] = 142        self.freq_keys[1][key] = None43        self.min_freq = 1

Time complexityO(1) average per get and putOptimized

Space complexityO(capacity)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoftBloomberg

LFU Cache

LFU Cache

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design