⚡Flashcard Drill➔
NeetCode #340LC-460HardLinked ListNC 250
← Back to All Problems

#340 · #460 · LFU Cache(LFU 缓存)

📌 Problem Statement & Constraints

Design a Least Frequently Used (LFU) cache with a fixed capacity. get(key) and put(key, value) must run in O(1). On eviction, remove the least frequently used key; ties are broken by least recent use. Constraints: 0 <= capacity <= 10^4; at most 2 * 10^5 calls.

💡 Core Algorithmic Approaches

  1. Three structures: a map from key to value, a map from key to frequency, and a map from frequency to an ordered set of keys at that frequency.
  2. The ordered set (an OrderedDict) at each frequency stores keys in usage order, so the first key is the least recently used at that frequency.
  3. Track min_freq so eviction is O(1) rather than requiring a scan over frequencies.
  4. On any access, move the key from frequency f to f + 1 and update min_freq if the old frequency bucket became empty.

💻 Benchmark Python3 Implementation

class LFUCache:
    def __init__(self, capacity: int):
        from collections import OrderedDict, defaultdict
        self.cap = capacity
        self.vals = {}                     # key -> value
        self.freqs = {}                    # key -> frequency
        self.buckets = defaultdict(OrderedDict)   # freq -> keys in usage order
        self.min_freq = 0

    def _touch(self, key: int) -> None:
        f = self.freqs[key]
        del self.buckets[f][key]           # leave the old frequency bucket
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1      # the minimum only ever rises by 1
        self.freqs[key] = f + 1
        self.buckets[f + 1][key] = None

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

    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:
            return                         # a zero-capacity cache stores nothing
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) >= self.cap:
            # evict the LRU key within the least frequent bucket
            lfu, _ = self.buckets[self.min_freq].popitem(last=False)
            del self.vals[lfu]
            del self.freqs[lfu]
        self.vals[key] = value
        self.freqs[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1                  # a newly inserted key has frequency 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per operation: each step is a constant number of dictionary and OrderedDict operations.
💾 Space Complexity
O(capacity) for the three maps.

⚠️ Interview Pitfalls & Follow-ups

  • Using a heap keyed by frequency: ties must be broken by recency, which a heap cannot do in O(1); the per-frequency ordered bucket handles it directly.
  • Not updating min_freq when a bucket empties: eviction would then target an empty bucket. The min_freq only needs to rise by 1, never more.
  • Forgetting to reset min_freq = 1 on a new insertion: a fresh key always has frequency 1, so the minimum is at most 1.
  • Handling capacity == 0: every put must be a no-op and every get must return -1; without the guard, the eviction code would index an empty bucket.
  • Confusing LRU and LFU tie-breaking: LFU evicts the least frequent, and only uses recency as a tie-breaker.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems