AlgoMaster Logo

LFU Cache

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We need to build a cache with a twist. Unlike LRU Cache (which evicts the least recently used item), LFU Cache tracks how many times each key has been accessed and evicts the one used the fewest times. When multiple keys share the same frequency, we break the tie using LRU ordering, evicting whichever was accessed least recently among them.

So there are two dimensions to manage: frequency counts and recency within each frequency. The challenge is doing this in O(1) time for both get and put. That rules out sorting, scanning, and log(n) data structures like heaps or balanced BSTs.

Two operations have to be fast: finding the minimum frequency, and within that frequency group, finding and removing the least recently used item. A combination of hash maps and linked lists handles both.

Key Constraints:

  • 1 <= capacity <= 10^4. The O(1) requirement is stated explicitly in the problem, so a small cache size is no excuse for a slower approach.
  • 0 <= key <= 10^5. Keys are non-negative integers, but a key array of size 10^5 wastes space when the cache holds far fewer entries, so a hash map is the general choice.
  • At most 2 * 10^5 calls. With 200K operations, an O(n) per-operation approach reaches roughly 2 * 10^9 basic steps in the worst case and times out. An O(log n) heap approach passes but does not meet the O(1) requirement.

Approach 1: Brute Force (Linear Scan)

Intuition

Store everything in a single hash map and handle eviction by scanning. For each key, track its value, its frequency count, and the timestamp of its last access. When eviction is needed, scan all entries to find the one with the lowest frequency, breaking ties by oldest timestamp.

This does not meet the O(1) requirement, but it gets the eviction rule correct and sets up the optimization that follows.

Algorithm

  1. Maintain a hash map where each key maps to a triple: (value, frequency, lastUsed).
  2. Keep a global counter time that increments on every get or put call.
  3. For get(key): if key exists, increment its frequency, update its lastUsed to current time, and return its value. Otherwise return -1.
  4. For put(key, value): if key exists, update its value, increment frequency, update lastUsed. If key doesn't exist and cache is full, scan all entries to find the one with the minimum frequency (break ties by minimum lastUsed), remove it, then insert the new key with frequency=1.

Example Walkthrough

1put(1,1): Insert key 1 with val=1, freq=1, time=0
1
:
[1,f=1,t=0]
1/6

Code

The O(n) scan on every eviction is the bottleneck. A min-heap ordered by the eviction priority removes the need to scan, bringing eviction down to O(log n).

Approach 2: Heap-Based (O(log n))

Intuition

Instead of scanning all entries to find the minimum, use a min-heap (priority queue) ordered by (frequency, lastUsed). The top of the heap is always the eviction candidate, which brings eviction down from O(n) to O(log n).

The complication is updates. When get is called on a key, its frequency and last-used time change, but a binary heap cannot update an arbitrary element efficiently. The workaround is lazy deletion: push a fresh entry for the key on every change and leave the old entry in the heap. During eviction, pop entries and skip any whose (frequency, lastUsed) no longer matches what the hash map records for that key.

Algorithm

  1. Maintain a hash map keyToEntry mapping each key to (value, frequency, lastUsed).
  2. Maintain a min-heap ordered by (frequency, lastUsed). Each heap entry stores (frequency, lastUsed, key).
  3. For get(key): look up in hash map, increment frequency, update lastUsed, push a new entry into the heap (the old one becomes stale).
  4. For put(key, value): if key exists, update it like get. If not, evict if full. To evict, pop from the heap until we find an entry whose (frequency, lastUsed) matches the current state in the hash map (skip stale entries). Remove that key. Then insert the new key.

Example Walkthrough

1put(1,1): Insert key 1 with freq=1, time=0
1
:
[1, 1, 0]
1/6

Code

The heap gives O(log n) per operation, but the problem asks for O(1). Two facts about LFU make the heap unnecessary: frequencies only ever increase by 1, and only the minimum frequency is ever queried. Grouping keys by frequency and tracking the minimum directly turns every operation into O(1).

Approach 3: Optimal - HashMap + Frequency Buckets with Doubly Linked Lists

Intuition

Because frequencies only increase by 1 and only the minimum is ever queried, no heap or sorted structure is needed.

Organize keys into frequency buckets. Bucket 1 holds all keys accessed once, bucket 2 holds keys accessed twice, and so on. Within each bucket, keys are ordered by recency using a doubly linked list: most recently used at the tail, least recently used at the head.

To evict, go to the bucket at minFreq and remove the head of its list (the least recently used key in the minimum-frequency group). That is O(1).

When a key's frequency increases from f to f+1, remove its node from bucket f's list and add it to bucket f+1's list. Both steps are O(1) because the hash map gives a direct pointer to the node, and a doubly linked list removes or inserts a known node in constant time.

The remaining question is how to keep minFreq correct without scanning. It changes in exactly two situations: inserting a brand new key resets it to 1, and emptying the bucket at minFreq during a promotion increments it by 1.

Algorithm

  1. Maintain three data structures:
    • keyToNode: hash map from key to its doubly linked list node (which stores key, value, and frequency).
    • freqToList: hash map from frequency to a doubly linked list of all keys with that frequency.
    • minFreq: integer tracking the current minimum frequency.
  2. For get(key): if key doesn't exist, return -1. Otherwise, remove the node from its current frequency list, increment its frequency, add it to the new frequency's list. If the old frequency list is now empty and equals minFreq, increment minFreq. Return the value.
  3. For put(key, value): if capacity is 0, return. If key exists, update its value and call the same frequency-promotion logic as get. If key doesn't exist and cache is full, evict the head node from freqToList[minFreq]. Create a new node with frequency 1, add it to freqToList[1], and set minFreq = 1.

Example Walkthrough

1put(1,1): Insert key 1 into freq=1 list. minFreq=1
1
:
[key1]
1/7

Code