LFU Cache

Difficulty: Hard Source: NeetCode

Problem

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement the LFUCache class:

LFUCache(capacity) — Initialize the LFU cache with the given capacity.

get(key) — Return the value of key if it exists, otherwise return -1. Accessing a key increments its frequency.

put(key, value) — Insert or update the key-value pair. If the number of keys exceeds capacity after insertion, evict the least frequently used key. Ties are broken by evicting the least recently used (LRU) among those with the same frequency.

Both get and put must run in O(1) average time complexity.

Example 1: Input: [“LFUCache”,“put”,“put”,“get”,“put”,“get”,“put”,“get”,“get”,“get”] [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]] Output: [null,null,null,1,null,-1,null,-1,3,4]

Constraints:

1 <= capacity <= 10^4

0 <= key <= 10^5

0 <= value <= 10^9

At most 2 * 10^5 calls will be made to get and put

Prerequisites

Before attempting this problem, you should be comfortable with:

LRU Cache — the same doubly-linked-list + hash map pattern (see problem 11)
OrderedDict — maintains insertion order, supports O(1) move to end
Min-Frequency Tracking — maintaining the current minimum frequency for O(1) eviction

1. Hash Maps + OrderedDict per Frequency (Optimal)

Intuition

LFU is harder than LRU because eviction depends on frequency, not just recency. But among keys with the same (minimum) frequency, we still evict the LRU one. So the structure is:

key_to_val — maps key → value
key_to_freq — maps key → current frequency
freq_to_keys — maps frequency → OrderedDict of keys (preserves insertion/access order for LRU tie-breaking)
min_freq — the current minimum frequency (the frequency bucket we evict from)

On get(key):

Return -1 if not found.
Increment key_to_freq[key].
Move the key from its old frequency bucket to the new one.
If the old bucket was min_freq and is now empty, increment min_freq.
Return the value.

On put(key, value):

If key already exists, update its value and call the same “increment frequency” logic as get.
If key is new, check capacity. If full, evict the LRU from freq_to_keys[min_freq].
Insert the new key with frequency 1. Set min_freq = 1.

The OrderedDict per frequency bucket gives us LRU ordering within each bucket — popitem(last=False) removes the oldest entry.

Algorithm

_increment_freq(key): Remove key from freq_to_keys[old_freq]. If old_freq == min_freq and bucket is now empty, min_freq += 1. Add key to freq_to_keys[new_freq] (at the end = MRU within that bucket).
get(key): If not found return -1. Else _increment_freq(key), return key_to_val[key].
put(key, value): If cap == 0, return. If key exists, update value, _increment_freq(key). Else if at capacity, evict LFU/LRU. Insert new key with freq=1, min_freq=1.

Solution

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.key_to_val = {}                          # key -> value
        self.key_to_freq = {}                         # key -> frequency
        self.freq_to_keys = defaultdict(OrderedDict)  # freq -> OrderedDict{key: None}
        self.min_freq = 0

    def _increment_freq(self, key: int):
        freq = self.key_to_freq[key]
        # Remove from current frequency bucket
        del self.freq_to_keys[freq][key]
        # If this was the minimum frequency bucket and it's now empty, bump min_freq
        if freq == self.min_freq and not self.freq_to_keys[freq]:
            self.min_freq += 1
        # Add to new frequency bucket (at end = most recently used in this freq)
        new_freq = freq + 1
        self.key_to_freq[key] = new_freq
        self.freq_to_keys[new_freq][key] = None

    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._increment_freq(key)
        return self.key_to_val[key]

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return

        if key in self.key_to_val:
            # Update existing key
            self.key_to_val[key] = value
            self._increment_freq(key)
        else:
            # Evict if at capacity
            if len(self.key_to_val) >= self.cap:
                # Remove LRU from the minimum frequency bucket
                lfu_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
                del self.key_to_val[lfu_key]
                del self.key_to_freq[lfu_key]

            # Insert new key with frequency 1
            self.key_to_val[key] = value
            self.key_to_freq[key] = 1
            self.freq_to_keys[1][key] = None
            self.min_freq = 1

# Test cases from the problem
cache = LFUCache(2)
cache.put(1, 1)     # freq[1]=1
cache.put(2, 2)     # freq[2]=1
print(cache.get(1)) # 1   freq[1]=2
cache.put(3, 3)     # evict key 2 (freq=1, LRU among freq-1 keys); freq[3]=1
print(cache.get(2)) # -1  (evicted)
print(cache.get(3)) # 3   freq[3]=2
cache.put(4, 4)     # evict key 4? no -- evict LFU: both 3 and 1 have freq=2? No.
                    # min_freq=1 (only key 4's freq=1 after insert), evict key 3? Let's trace.
                    # Actually: after put(3,3): cache={1:freq2, 3:freq1}, min_freq=1
                    # get(3): freq[3]=2, min_freq bumps to 2 (freq-1 bucket now empty)
                    # cache={1:freq2, 3:freq2}, min_freq=2
                    # put(4): at capacity(2), evict from freq-2 bucket. LRU is key 1 (inserted first). Evict 1.
                    # Insert 4 with freq=1, min_freq=1
print(cache.get(1)) # -1  (evicted)
print(cache.get(3)) # 3   freq[3]=3
print(cache.get(4)) # 4   freq[4]=2

print("---")

# Simpler test: verify LRU tie-breaking
cache2 = LFUCache(3)
cache2.put(1, 1)
cache2.put(2, 2)
cache2.put(3, 3)
# All have freq=1. Access 1 and 2 to give them freq=2.
cache2.get(1)
cache2.get(2)
# Now freq[1]=2, freq[2]=2, freq[3]=1. min_freq=1.
# Put 4 -> evicts LFU = key 3 (only key with freq=1)
cache2.put(4, 4)
print(cache2.get(3))  # -1 (evicted)
print(cache2.get(1))  # 1
print(cache2.get(2))  # 2
print(cache2.get(4))  # 4

print("---")

# Edge: capacity 1
cache3 = LFUCache(1)
cache3.put(1, 1)
cache3.put(2, 2)     # evicts 1
print(cache3.get(1)) # -1
print(cache3.get(2)) # 2

Complexity

Time: O(1) average for both get and put — all dictionary and OrderedDict operations are O(1) amortized
Space: O(capacity) — bounded by number of stored keys

Not updating min_freq on insertion. When you insert a brand new key, its frequency is always 1, so min_freq = 1. Forgetting to reset min_freq means you’ll try to evict from the wrong (possibly empty) frequency bucket.

Not bumping min_freq after _increment_freq. If the old min_freq bucket becomes empty after incrementing a key’s frequency, min_freq must increase. But only increase it by 1 — you can’t skip frequencies because the new frequency is guaranteed to be old + 1.

Confusing LFU with LRU. LRU evicts the key that was accessed the longest time ago. LFU evicts the key that has been accessed the fewest total times (with LRU as tie-breaker). The OrderedDict within each frequency bucket handles the tie-breaking: popitem(last=False) removes the key that was added to that bucket earliest = the LRU within that frequency group.

Handling capacity 0. The constraints say capacity >= 1, but it’s good practice to guard against it. If cap == 0, put should do nothing.

Note Book