AlgoViz
HomeStack

LFU Cache

Hard

One list per frequency, plus a minimum

Problem

Design a Least-Frequently-Used cache with O(1) get and put (ties broken by least recent).

In simple words

Group items by how often they're used; evict from the least-used group, oldest first.

The idea

Keep a map from key to node, a map from frequency to a list of nodes at that frequency, and the current minimum frequency. Using a key moves its node to the next frequency's list, and eviction takes the least-recent node from the minimum-frequency list.

The trick

  • Ties within a frequency are broken by recency, which is why each bucket is an ordered list.
  • The minimum frequency only increases on access, or resets to 1 on insert.
  • All operations stay O(1).

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
0

Step 1 of 2. Here's the example — cap=2; operations Values: 2.

1/2
Optimal
timeO(1)spaceO(cap)
1maps: key->(value,freq), freq->ordered list of keys2get/put: bump freq, move key to next freq bucket3evict from smallest freq bucket

Input

array
[2]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
cap=2; operations
Output:
evict least used

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.