04. LFU Cache (Least Frequently Used)

Difficulty:HardPattern:Doubly Linked List + MapTime:O(1) Get / PutSpace:O(capacity)

Design and implement a data structure for a Least Frequently Used (LFU) cache supporting get and put operations in $O(1)$ time complexity.

How It Works & Algorithmic Design

Solves using Hash Map + Doubly Linked Frequency Lists:

Key Map: keyMap[key] = node (stores value, frequency, key reference).
Frequency Map: freqMap[freq] = DoublyLinkedList (LRU ordered list for nodes sharing the same access frequency).
Track Min Frequency: Maintain variable minFreq.
Operations:
- get(key): If present, increment node frequency, update doubly linked lists, update minFreq, return node value.
- put(key, val): If key exists, update value and bump frequency. If new and full capacity reached, remove tail node from freqMap[minFreq]. Insert new node with frequency 1 and set minFreq = 1.

Why This Approach Works Best

Doubly linked frequency buckets achieve strict constant $O(1)$ time for both cache lookup and frequency displacement.

Example Walkthrough

Operations: put(1,1), put(2,2), get(1), put(3,3)

Capacity 2 LFU cache.

Eviction: key 2 has freq 1, key 1 has freq 2. Key 2 evicted when adding key 3.

Least frequent node removed.

Output: get(1)->1, get(2)->-1 (evicted), get(3)->3

Cache responses.

Answer: LFU Cache $O(1)$ implementation

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.minFreq = 0;
    this.keyMap = new Map();
    this.freqMap = new Map();
  }
  _update(node) {
    const oldFreq = node.freq;
    const oldList = this.freqMap.get(oldFreq);
    oldList.delete(node);
    if (oldFreq === this.minFreq && oldList.size === 0) this.minFreq++;
    node.freq++;
    if (!this.freqMap.has(node.freq)) this.freqMap.set(node.freq, new Set());
    this.freqMap.get(node.freq).add(node);
  }
  get(key) {
    if (!this.keyMap.has(key)) return -1;
    const node = this.keyMap.get(key);
    this._update(node);
    return node.val;
  }
  put(key, value) {
    if (this.capacity === 0) return;
    if (this.keyMap.has(key)) {
      const node = this.keyMap.get(key);
      node.val = value;
      this._update(node);
    } else {
      if (this.keyMap.size >= this.capacity) {
        const minList = this.freqMap.get(this.minFreq);
        const evictNode = minList.values().next().value;
        minList.delete(evictNode);
        this.keyMap.delete(evictNode.key);
      }
      const newNode = { key, val: value, freq: 1 };
      this.keyMap.set(key, newNode);
      this.minFreq = 1;
      if (!this.freqMap.has(1)) this.freqMap.set(1, new Set());
      this.freqMap.get(1).add(newNode);
    }
  }
}

💡 Store frequency nodes in doubly linked list buckets mapped by frequency keys for O(1) eviction.

Key Takeaways

Use frequency maps storing doubly linked lists to track duplicate frequency tie breaks.
Increments minFreq when lowest frequency bucket empties out.
Guarantees $O(1)$ operations for get and put.