LFU Cache

Problem in Plain English

Build a fixed-capacity cache that evicts the least frequently used key, breaking frequency ties by least recent use. Both get and put must run in constant time.

Problem Statement

Design a Least Frequently Used (LFU) cache with a fixed capacity. get(key) returns the stored value and raises the key's frequency, or returns -1 when absent without changing the cache. put(key, value) inserts a new key at frequency 1, or updates an existing key and raises its frequency exactly once. Both successful reads and updates count as uses and refresh recency.

Before inserting into a full cache, evict the key with the smallest frequency; among tied keys, evict the least recently used. A capacity of 0 stores nothing. The required design supports each operation in expected $O(1)$ time under constant-time hash-map operations; a scanning baseline below explains the bottleneck.

Constraints

$0 \leq capacity \leq 10^4$
$0 \leq key \leq 10^5$
$0 \leq value \leq 10^9$
At most $2 \times 10^5$ calls are made to get and put.

Examples

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]

The constructor and writes return null. Reading key 1 raises it to frequency 2, so inserting key 3 evicts key 2 at frequency 1. Reading absent key 2 returns -1 without changing state. Reading key 3 creates a frequency-2 tie; key 1 was used earlier, so inserting key 4 evicts key 1. The final reads return -1, 3, and 4.

Example 2

Input: ["LFUCache", "put", "get"] [[0], [1, 1], [1]]
Output: [null, null, -1]

A zero capacity stores nothing, so the later get misses and returns -1.

Example 3

Input: ["LFUCache", "put", "put", "put", "put", "get", "get", "get"] [[2], [0, 0], [1, 10], [0, 7], [2, 20], [1], [0], [2]]
Output: [null, null, null, null, null, -1, 7, 20]

Updating key 0 changes its value from 0 to 7 and increases its frequency from 1 to 2. Inserting key 2 therefore evicts key 1 at frequency 1, even though key 0 was inserted first. The miss returns -1; the survivors return their current values 7 and 20. Key and value zero are valid and must not be treated as absence.

Intuition

Frequency answers how often a key has been used; recency answers which tied key was used least recently. In Example 1, reading key 1 raises its frequency to 2, so inserting key 3 evicts key 2 at frequency 1. After reading key 3, both survivors have frequency 2, but key 1 is older and loses the next eviction tie. Keep a separate recency list for each frequency and remember the smallest occupied frequency: together they identify the victim without scanning. Updating an existing value is also a use, while a missed read changes neither frequency nor recency.

Approaches

Scan For Eviction

Solution Details

Reveal Scan For Eviction: intuition, complexity, and code

Intuition

Store each key with its value, frequency, and a recency stamp, then scan the whole cache to elect the eviction victim. The scan is simple to reason about but repeats linear work on every full put.

Step-by-Step Logic

Store value, frequency, and a monotonically increasing use timestamp for each resident key. Start Example 1 with capacity 2, an empty map, and clock 0.
On a successful get or existing-key put, increase frequency once and assign the next timestamp; a miss leaves everything unchanged. After put(1, 1), put(2, 2), and get(1), key 1 has (frequency 2, stamp 3) and key 2 has (frequency 1, stamp 2).
Before inserting a new key into a full cache, scan all residents and minimize the pair (frequency, timestamp). put(3, 3) chooses key 2; insert key 3 with frequency 1 and stamp 4.
After get(3), keys 1 and 3 both have frequency 2. For put(4, 4), key 1's stamp 3 is older than key 3's stamp 5, so evict key 1.
Insert every new key at frequency 1 and the newest timestamp. Continue the remaining reads: get(1) misses, get(3) returns 3, and get(4) returns 4. Capacity 0 makes every write a no-op.

Why It Works

Inductively, each map entry holds the latest value, the exact number of insertions and successful uses since that key entered the cache, and the timestamp of its latest use. New insertions start at frequency 1; successful reads and updates increment it exactly once; misses leave the invariant unchanged. Timestamps strictly increase, so minimizing (frequency, timestamp) selects the LFU key and then the oldest key among all frequency ties. The scan considers every resident, hence cannot miss a better victim. Evicting before insertion keeps the number of entries at most capacity.

Dry Run

Scan For Eviction: variable states at each step
Call	Clock	Residents: key → (value, frequency, stamp)	Victim / result
LFUCache(2)	0	{}	null
put(1, 1)	1	{1: (1, 1, 1)}	null
put(2, 2)	2	{1: (1, 1, 1), 2: (2, 1, 2)}	null
get(1)	3	{1: (1, 2, 3), 2: (2, 1, 2)}	1
put(3, 3)	4	{1: (1, 2, 3), 3: (3, 1, 4)}	evict 2: frequency 1; null
get(2)	4	{1: (1, 2, 3), 3: (3, 1, 4)}	-1; unchanged
get(3)	5	{1: (1, 2, 3), 3: (3, 2, 5)}	3
put(4, 4)	6	{3: (3, 2, 5), 4: (4, 1, 6)}	evict 1: tied frequency 2, older stamp 3; null
get(1)	6	{3: (3, 2, 5), 4: (4, 1, 6)}	-1; unchanged
get(3)	7	{3: (3, 3, 7), 4: (4, 1, 6)}	3
get(4)	8	{3: (3, 3, 7), 4: (4, 2, 8)}	4; full output [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Complexity Analysis

Time Complexity

O(c+1)

Space Complexity

O(c+1)

Let c be capacity. Successful reads, misses, updates, and non-full insertions take expected O(1) time; a new insertion into a full positive-capacity cache scans c residents, so worst-case time per call is O(c + 1). Hash-map storage grows to at most c resident entries and is O(c + 1), including the empty cache's fixed overhead. Across q calls, worst-case time is O(q(c + 1)); this baseline does not meet the required constant-time eviction. At most 200000 calls keep frequency and clock within Java int and exact JavaScript integer bounds.

Code

Solution.java

1import java.util.HashMap;2import java.util.Map;3
4class LFUCache {5    private static class Entry {6        int val;7        int freq;8        int stamp;9        Entry(int val, int freq, int stamp) {10            this.val = val;11            this.freq = freq;12            this.stamp = stamp;13        }14    }15
16    private int capacity;17    private int clock;18    private Map<Integer, Entry> cache;19
20    public LFUCache(int capacity) {21        this.capacity = capacity;22        this.clock = 0;23        this.cache = new HashMap<>();24    }25
26    public int get(int key) {27        if (!cache.containsKey(key)) {28            return -1;29        }30        Entry e = cache.get(key);31        e.freq++;32        e.stamp = ++clock;33        return e.val;34    }35
36    public void put(int key, int value) {37        if (capacity == 0) {38            return;39        }40        if (cache.containsKey(key)) {41            Entry e = cache.get(key);42            e.val = value;43            e.freq++;44            e.stamp = ++clock;45            return;46        }47        if (cache.size() == capacity) {48            int victim = -1;49            int bestFreq = Integer.MAX_VALUE;50            int bestStamp = Integer.MAX_VALUE;51            // Lexicographic (frequency, stamp) order implements LFU then LRU.52            for (Map.Entry<Integer, Entry> kv : cache.entrySet()) {53                Entry e = kv.getValue();54                if (e.freq < bestFreq || (e.freq == bestFreq && e.stamp < bestStamp)) {55                    bestFreq = e.freq;56                    bestStamp = e.stamp;57                    victim = kv.getKey();58                }59            }60            cache.remove(victim);61        }62        cache.put(key, new Entry(value, 1, ++clock));63    }64}

Hints

Hint 1

A plain map finds keys instantly, but choosing the eviction victim by scanning every entry costs linear time.

Hint 2

Group keys by frequency so the eviction candidate always sits in the group with the smallest count.

Hint 3

Track the minimum frequency explicitly, keep each group in recency order with sentinel nodes, and move a key to the next group on every touch.

Edge Cases

Capacity 0: every put is a no-op and every get returns -1; there is no minimum occupied frequency.
Capacity 1: repeatedly reading the only key must leave exactly one nonempty frequency group. A new key still evicts that key regardless of how large its frequency became.
An existing-key put is a successful use: update its value, increment frequency, and refresh recency without evicting any key, even when full.
If several residents share the minimum frequency, eviction removes the oldest successful use in that group. A missed read must not refresh recency.
A large gap between occupied frequencies is valid. Only promotion of the last minimum node allows minFreq += 1; eviction instead relies on the incoming frequency-1 node.
Key 0, value 0, and value 1000000000 are legal. Use map membership rather than truthiness to distinguish a stored zero from an absent key.

Common Mistakes and Interview Tips

Updating the value on an existing-key put without increasing frequency and refreshing recency violates the use-count contract.
Incrementing minFreq whenever any group empties is wrong; promotion changes it only if that group was the current minimum.
Retaining empty frequency groups after promotion or eviction leaks one sentinel list per historical frequency; capacity 1 with many reads exposes this.
Trying to advance minFreq by one after eviction can land on an empty frequency gap. Reset it to 1 when inserting the new node instead.
Removing an eviction victim only from the linked list leaves a ghost key mapping. Each resident must appear once in both structures.
Appending a touched node at the LRU end reverses the tie-breaking rule. Insert at the MRU front and evict from the tail.
Interview tip: distinguish frequency from global recency, state the group and minimum invariants, and explain why removing the last minimum node during promotion gives a known next minimum.

Key Takeaway

When priority changes by exactly one on a use, a key map plus ordered frequency buckets can maintain ranked eviction without a global sort. A known next rank handles promotion; an inserted rank-1 item restores the minimum after eviction. Reclaim empty buckets so the structure remains bounded by live capacity.