Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

  • LFUCache(int capacity) Initializes the object with the capacity of the data structure.
  • int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
  • void put(int key, int value) Update or insert the value. If the key already exists, update the value. If the key does not exist, insert the key-value pair. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

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]

Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the key-value pairs in the order they were inserted.

LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[4,3], cnt(4)=2, cnt(3)=3

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.

Thinking Process

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.
  • Slow/fast pointers find middle or detect cycles in one pass.
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

Time Complexity: O(1) for both get and put
Space Complexity: O(capacity)

We use two hash maps:

  1. frequencies: Maps frequency → list of (key, value) pairs (ordered by recency)
  2. cache: Maps key → (frequency, iterator) pair

When there’s a tie in frequency, we use the least recently used key (front of the list).

Solution: Optimized Python20 Version

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val: dict[int, int] = {}
        self.key_to_freq: dict[int, int] = {}
        self.freq_to_keys: dict[int, OrderedDict] = defaultdict(OrderedDict)

    def _touch(self, key: int) -> None:
        f = self.key_to_freq[key]
        del self.freq_to_keys[f][key]
        if not self.freq_to_keys[f]:
            del self.freq_to_keys[f]
            if self.min_freq == f:
                self.min_freq += 1
        f += 1
        self.key_to_freq[key] = f
        self.freq_to_keys[f][key] = None

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

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._touch(key)
            return
        if len(self.key_to_val) >= self.capacity:
            k, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[k]
            del self.key_to_freq[k]
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: Design and implement a data structure for a Least Frequently Used (LFU) cache.

How the code works:

  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.
  • Slow/fast pointers find middle or detect cycles in one pass.

    Why This Design Works

  1. Frequency Lists: Each frequency has its own list, maintaining LRU order
  2. Min Frequency Tracking: Always know which frequency to evict from
  3. Iterator Storage: O(1) access to nodes for removal
  4. Tie Breaking: Front of list = least recently used (LRU)

Common Mistakes

  1. Capacity = 0 or 1: Handle empty cache
  2. Get non-existent key: Returns -1
  3. Update existing key: Promotes frequency, doesn’t increase size
  4. Tie in frequency: Evict least recently used (front of list)

  5. All keys have same frequency: Use LRU order

  6. Not updating min_frequency: Must track minimum frequency correctly
  7. Wrong eviction order: Evict from front of min_frequency list (LRU)
  8. Not handling empty frequency lists: Remove empty lists and update min_frequency
  9. Iterator invalidation: Be careful when modifying lists
  10. Forgetting to promote on put update: Must increment frequency when updating existing key

Comparison: LRU vs LFU

Aspect LRU Cache LFU Cache
Eviction Policy Least Recently Used Least Frequently Used
Tie Breaking N/A (single order) Least Recently Used
Complexity O(1) O(1)
Use Case Temporal locality Frequency-based access

Key Takeaways

  • Pattern: Iterative pointer walk (this problem)
  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.

References