Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
LFU Cache
Bookmark
Linear Scan
Min-Heap
Freq Buckets
Input
LeetCode Example
Eviction
Capacity 1
Custom
operations
=
[LFUCache, put, put, get, put, get, get, put, get, get, get]
,
values
=
[2, 1,1, 2,2, 1, 3,3, 2, 3, 4,4, 1, 3, 4]
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)
=
?
freq 1
cache is empty
minFreq
0
· size
0 / 2
promote on access · evict the LRU key of the minFreq bucket
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)
=
?
freq 1
cache is empty
minFreq
0
· size
0 / 2
promote on access · evict the LRU key of the minFreq bucket
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)
=
?
freq 1
min
↑ evict LRU
1
:
1
minFreq
1
· size
1 / 2
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)
=
?
freq 1
min
↑ evict LRU
1
:
1
2
:
2
minFreq
1
· size
2 / 2
LFUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
?
get(3)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
freq 1
min
↑ evict LRU
freq 2
1
:
1
2
:
2
minFreq
1
· size
2 / 2
call
put(3, 3)
LFUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
?
get(3)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
freq 1
min
↑ evict LRU
freq 2
1
:
1
3
:
3
minFreq
1
· size
2 / 2
LFUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
get(3)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
freq 1
freq 2
min
↑ evict LRU
1
:
1
3
:
3
minFreq
2
· size
2 / 2
freq 1 bucket empty ·
minFreq → 2
LFUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
get(3)
=
3
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
freq 1
freq 2
min
↑ evict LRU
1
:
1
3
:
3
minFreq
2
· size
2 / 2
evict LRU of freq 2:
key 1
LFUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
get(3)
=
3
put(4, 4)
get(1)
=
-1
get(3)
=
?
get(4)
=
?
freq 1
min
↑ evict LRU
freq 2
3
:
3
4
:
4
minFreq
1
· size
2 / 2
1
not cached
→ -1
LFUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
get(3)
=
3
put(4, 4)
get(1)
=
-1
get(3)
=
3
get(4)
=
?
freq 1
min
↑ evict LRU
freq 2
freq 3
3
:
3
4
:
4
minFreq
1
· size
2 / 2
call
get(4)
LFUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
get(3)
=
3
put(4, 4)
get(1)
=
-1
get(3)
=
3
get(4)
=
4
freq 1
freq 2
min
↑ evict LRU
freq 3
3
:
3
4
:
4
minFreq
2
· size
2 / 2
All operations processed
algo
master
.
io
Step:
LFU Cache (capacity 2): frequency buckets + a minFreq pointer for O(1) eviction of the least-frequently, least-recently used key.
0 / 63
Input
LeetCode Example
Eviction
Capacity 1
Custom
operations
=
[LFUCache, put, put, get, put, get, get, put, get, get, get]
,
values
=
[2, 1,1, 2,2, 1, 3,3, 2, 3, 4,4, 1, 3, 4]
0 / 63
algo
master
.
io
Step:
LFU Cache (capacity 2): frequency buckets + a minFreq pointer for O(1) eviction of the least-frequently, least-recently used key.
