LeetCode #460 Hard

LFU Cache

O(1) cache evicting the least frequently used key; ties broken by least recent.

designhash-tablelfu

02

Intuition

💡

Group keys by use-count: freq → an ordered set of keys (insertion order = recency). Track the minimum frequency. A touch moves a key from bucket f to f+1; eviction pops the oldest key from the min-freq bucket. Every step is a dict/OrderedDict operation — O(1).

03

Approach

1

Two maps + a counter

vals key→(value,freq); buckets freq→OrderedDict of keys; minf = current lowest frequency.

2

Touch promotes

Remove key from bucket f; add to bucket f+1. If bucket f was the min and is now empty, minf += 1 (the only way minf rises).

3

Insert resets minf

A new key has freq 1 → minf = 1. Eviction (before insert, when full): popitem(last=False) on bucket minf = oldest of the least-used.

04

Solution & live demo

python

▶1from collections import defaultdict, OrderedDict
▶2 
▶3class LFUCache:
▶4    def __init__(self, capacity):
▶5        self.cap = capacity
▶6        self.vals = {}                        # key -> [value, freq]
▶7        self.buckets = defaultdict(OrderedDict)  # freq -> keys (ordered)
▶8        self.minf = 0
▶9 
▶10    def _touch(self, key):
▶11        value, f = self.vals[key]
▶12        del self.buckets[f][key]
▶13        if self.minf == f and not self.buckets[f]:
▶14            self.minf = f + 1
▶15        self.buckets[f + 1][key] = None
▶16        self.vals[key][1] = f + 1
▶17 
▶18    def get(self, key):
▶19        if key not in self.vals: return -1
▶20        self._touch(key)
▶21        return self.vals[key][0]
▶22 
▶23    def put(self, key, value):
▶24        if self.cap == 0: return
▶25        if key in self.vals:
▶26            self.vals[key][0] = value
▶27            self._touch(key); return
▶28        if len(self.vals) == self.cap:
▶29            old, _ = self.buckets[self.minf].popitem(last=False)
▶30            del self.vals[old]
▶31        self.vals[key] = [value, 1]
▶32        self.buckets[1][key] = None
▶33        self.minf = 1

05

Edge cases

put on existing key

Value update counts as a use — promote, don't evict.

capacity 0

Every put is a no-op; guard first.

06

Complexity

Time

O(1) per op

Space

O(capacity)

OrderedDict gives O(1) oldest-key eviction.