Implementing LFU (Least Frequently Used) Cache in C++ / Java (LeetCode Hard)

1. Overview and Problem Statement

An LFU (Least Frequently Used) Cache is an advanced data structure used to store a limited number of key-value pairs. When the cache reaches its maximum capacity and a new element needs to be inserted, the system evicts the item that has been accessed the fewest number of times. If there is a tie (multiple items with the same lowest frequency), the cache evicts the least recently used item among them (utilizing an internal LRU tie-breaker strategy).

Unlike an LRU cache—which can be implemented with a simple doubly linked list and a hash map in strict $O(1)$ time—an LFU cache requires tracking both access frequency and recency. To achieve true $O(1)$ time complexity for both get and put operations, we must use a sophisticated multi-map and doubly linked list architecture.

2. Core Mental Model and Architecture

To achieve $O(1)$ operations, we cannot afford to search through elements or iterate over lists during evictions. We need direct pointers to data nodes and grouped frequency buckets.

The Component Maps

1. Key-Node Map (keyMap): Maps every key directly to its corresponding memory node (Key -> Node* in C++ or Key -> Node in Java). This enables $O(1)$ lookups for get().
2. Frequency-List Map (freqMap): Maps an integer frequency to a doubly linked list of nodes (Frequency -> DoublyLinkedList). All nodes in a specific list share the exact same access frequency.
3. Tracking Variables:
   • capacity: The maximum number of elements the cache can hold.
   • size: The current number of elements in the cache.
   • minFreq: A running integer tracking the minimum frequency currently present in the cache. This is vital for $O(1)$ evictions because when capacity is exceeded, we instantly know which frequency bucket contains the victim to evict.

3. The Node Structure

Every node stored in the cache must contain metadata to support both bidirectional list traversal and frequency tracking:

• key: The cache key.
• value: The data associated with the key.
• frequency: How many times this key has been accessed (initialized to 1 on creation).
• prev / next: Pointers to adjacent nodes in the frequency doubly linked list.

4. Doubly Linked List Mechanics for Frequency Buckets

Each frequency bucket maintains its own doubly linked list with dummy head and tail sentinel nodes to avoid edge-case checks for null pointers.

Essential List Operations:

• addFront(Node* node): Inserts a newly accessed or newly created node right after the dummy head (making it the most recently used among that frequency).
• removeNode(Node* node): Detaches a node from its current doubly linked list in $O(1)$ time by updating its neighbor pointers.
• Eviction Tracking: Because new items are added to the front, the least recently used item for a given frequency sits right before the dummy tail (or can be tracked via tail-based removal depending on implementation convention).

5. The get(key) Flow Walkthrough

When a user requests a key via get(key):

1. Check Existence: Look up the key in keyMap. If it does not exist, return -1.
2. Access & Update Frequency: If the key exists, retrieve its associated Node.
3. Modify Frequency Grouping:
   • Because the node was accessed, its frequency increases by 1.
   • Remove the node from its current frequency list in freqMap.
   • MinFreq Check: If the list we just removed the node from becomes empty, and that frequency equalled minFreq, increment minFreq by 1 (since the lowest frequency level has now shifted up).
4. Relocate Node:
   • Update the node's internal frequency counter (frequency++).
   • Insert the node into the new frequency list (freqMap[newFreq]).
   • If the new frequency list did not exist, create it.
5. Return Value: Return node->value.

6. The put(key, value) Flow Walkthrough

When inserting or updating a key via put(key, value):

1. Capacity Validation: If capacity is 0, abort immediately.
2. Check if Key Already Exists:
   • If the key already exists, update its value and treat the operation like a get() call (increment its frequency and relocate it to the next frequency list).
3. If Key Does Not Exist (New Insertion):
   • Check if currentSize >= capacity.
   • Eviction Routine: If full, find the eviction victim using minFreq. Access freqMap[minFreq], grab the tail-most node (least recently used at the minimum frequency), remove it from the list, and delete its key from keyMap. Decrement currentSize.
   • Create New Node: Initialize a new node with frequency = 1, key, and value.
   • Reset MinFreq: Since a brand-new element is always inserted with frequency 1, reset minFreq = 1.
   • Insert into Maps: Add the new node to freqMap[1] (at the front) and store it in keyMap.
   • Increment currentSize.

7. Complexity Analysis

8. C++ Implementation Blueprint

Below is the structural blueprint demonstrating how the C++ classes (Node, DoublyLinkedList, and LFUCache) interact:

#include <unordered_map>
#include <iostream>

using namespace std;

class LFUCache {
private:
    struct Node {
        int key, val, freq;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), val(v), freq(1), prev(nullptr), next(nullptr) {}
    };

    struct List {
        int size;
        Node* head;
        Node* tail;
        List() {
            size = 0;
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head->next = tail;
            tail->prev = head;
        }
        
        void addFront(Node* node) {
            Node* nextNode = head->next;
            head->next = node;
            node->prev = head;
            node->next = nextNode;
            nextNode->prev = node;
            size++;
        }

        void removeNode(Node* node) {
            Node* prevNode = node->prev;
            Node* nextNode = node->next;
            prevNode->next = nextNode;
            nextNode->prev = prevNode;
            size--;
        }

        Node* removeTail() {
            if (size == 0) return nullptr;
            Node* node = tail->prev;
            removeNode(node);
            return node;
        }
    };

    int maxCapacity;
    int currentSize;
    int minFreq;
    unordered_map<int, Node*> keyMap;
    unordered_map<int, List*> freqMap;

    void updateFreq(Node* node) {
        int freq = node->freq;
        freqMap[freq]->removeNode(node);

        if (freq == minFreq && freqMap[freq]->size == 0) {
            minFreq++;
        }

        node->freq++;
        int newFreq = node->freq;
        
        if (freqMap.find(newFreq) == freqMap.end()) {
            freqMap[newFreq] = new List();
        }
        freqMap[newFreq]->addFront(node);
    }

public:
    LFUCache(int capacity) {
        maxCapacity = capacity;
        currentSize = 0;
        minFreq = 0;
    }
    
    int get(int key) {
        if (keyMap.find(key) == keyMap.end()) return -1;
        Node* node = keyMap[key];
        updateFreq(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if (maxCapacity == 0) return;

        if (keyMap.find(key) != keyMap.end()) {
            Node* node = keyMap[key];
            node->val = value;
            updateFreq(node);
            return;
        }

        if (currentSize >= maxCapacity) {
            List* minFreqList = freqMap[minFreq];
            Node* toRemove = minFreqList->removeTail();
            keyMap.erase(toRemove->key);
            delete toRemove;
            currentSize--;
        }

        currentSize++;
        minFreq = 1;
        Node* newNode = new Node(key, value);
        
        if (freqMap.find(minFreq) == freqMap.end()) {
            freqMap[minFreq] = new List();
        }
        
        freqMap[minFreq]->addFront(newNode);
        keyMap[key] = newNode;
    }
};

9. Real-World Debugging Pitfalls & Edge Cases

1. Zero Capacity Cache (capacity == 0):
   • Issue: If capacity is initialized to 0, any put operation will attempt eviction or insertion, resulting in segmentation faults or memory corruption if not guarded.
   • Fix: Always place an early return check if (maxCapacity == 0) return; at the beginning of put.
2. Forgetting to Update minFreq:
   • Issue: When removing the last node from a frequency list that matches minFreq, failing to increment minFreq causes subsequent insertions to look for a stale, empty frequency bucket.
   • Fix: Always verify if (freq == minFreq && freqMap[freq]->size == 0) minFreq++;.
3. Memory Leaks in C++:
   • Issue: Nodes removed during eviction must be explicitly deleted using delete to prevent memory leaks in long-running applications.
4. Stale Key References in keyMap:
   • Issue: When evicting a node from the minimum frequency list via removeTail(), developers sometimes forget to erase the corresponding key from keyMap.
   • Fix: Ensure keyMap.erase(toRemove->key) is executed immediately upon eviction.

10. Summary and Key Takeaways

• Definition: LFU (Least Frequently Used) cache evicts the element accessed the fewest times, using recency (LRU) as a tie-breaker.
• Time Complexity Goal: Achieving true $O(1)$ time complexity for both get and put requires a combination of hash maps and doubly linked lists.
• Key Data Structures:
  • keyMap (int -> Node*) for $O(1)$ lookups.
  • freqMap (int -> DoublyLinkedList) to group items by access frequency.
• Tracking minFreq: Maintaining a running minFreq variable allows the cache to locate eviction victims instantly without scanning through multiple lists.
• Dummy Sentinels: Utilizing dummy head and tail nodes in doubly linked lists simplifies insertion and removal logic by eliminating null-pointer checks.
• Frequency Promotion: Every time a key is accessed (get or put), its frequency increments by $1$, moving it to the next frequency bucket.
• Capacity Management: When currentSize exceeds maxCapacity, the tail node of the minFreq list is purged.