Algorithm

LFU Cache

Design Pattern

LFU Cache

Design a data structure that follows the constraints of a Least Frequently Used (LFU) cache. It must support O(1) time complexity for both get and put operations.

CONSTRAINTS
  • 0 <= capacity <= 10⁴
  • 0 <= key <= 10⁵
  • 0 <= value <= 10⁹
  • At most 2 × 10⁵ calls will be made to get and put
EXAMPLE 1
Input: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Key 2 is evicted when 3 is put because it was least frequently used. Later, key 1 is evicted because it became the LFU after other gets.
How do we decide which key to evict when frequencies are tied?
We apply an LRU policy within that specific frequency bucket. The key that was accessed least recently among those with the same count is evicted.
Does updating an existing key's value count as a 'use'?
Yes. Any 'get' or 'put' operation on a key increments its frequency and promotes it to the next bucket.

If LRU is a "Recency" policy, LFU is a "Popularity" policy. Imagine a library that tracks not just the most recently read books, but how many times each book has been read in total.

The Library of Shelves

Instead of one long line, we organize books into Frequency Shelves.
- There is a shelf for books read 1 time, a shelf for 2 times, and so on.
- Each shelf is itself a Doubly Linked List (DLL) where new arrivals go to the front.
- If we access a book on the "Freq 1" shelf, it is immediately "promoted" to the front of the "Freq 2" shelf.

The Eviction Crisis

When the library is full and a new book arrives:
1. We look for the lowest-numbered shelf that isn't empty (the minFreq).
2. On that shelf, we take the book at the very back (the one that hasn't been touched in the longest time—the LRU of that frequency).
3. We evict it to make room.

The O(1) Secret

To make this work at lightning speed, we use two maps:
- Map 1 (The Directory): Maps key -> Node. This lets us find any book instantly.
- Map 2 (The Shelves): Maps frequency -> DLL. This lets us find the "Freq 1" shelf or the "Freq 5" shelf instantly.

Worked Example:promotion, then an eviction that breaks a tie (capacity 2)
0
1
Freq 1
1
2
Freq 1
put(1, A), put(2, B): Both items are inserted with frequency 1. Shelf 1 has order [2, 1] (key 2 is newer). min_freq = 1.
0
2
Freq 1
1
1
Freq 2
get(1): Key 1 is accessed and its frequency increases to 2. Shelf 1: [2] (LRU). Shelf 2: [1] (MRU). min_freq remains 1.
0
3
Freq 1
1
1
Freq 2
put(3, C): Cache full. Evict LRU from min_freq 1 shelf, which evicts Key 2. Key 3 inserted at Freq 1. Cache is now [3, 1].
Interactive Strategy Visualization
FREQUENCY-BASED CACHE

Hierarchical DLL Architecture

INITIALIZING
EMPTY SYSTEM
HASH MAP

Hierarchy

  • Frequency Buckets: Keys with the same access count stay together.
  • Internal LRU: Each bucket is a DLL. We evict from the back of the lowest freq bucket.
Logic TraceSTEP 1/6
LFU Cache: Evicts the least frequently used item. Ties are broken by LRU policy.
LFU+LRU

Optimal Cache Policy

LFU is superior for frequency-heavy workloads. The hierarchical DLL structure ensures that both "promotion" and "eviction" take O(1) time.

O(N) Scan for Min Frequency
→
O(1) Frequency Buckets + Per-Bucket Recency