What is an LFU Cache?

LFU stands for Least Frequently Used. An LFU Cache is a fixed-capacity cache that evicts the item that has been accessed the fewest number of times when it runs out of space.

In simple words:

• The cache has a capacity (maximum number of key-value pairs it can hold).
• Every get() or put() on a key increases that key's usage frequency by 1.
• When the cache is full and a new key must be inserted, the key with the lowest frequency is evicted.
• If multiple keys share the same lowest frequency, the least recently used among them is evicted (this is the tie-breaking rule).

🧠 Think of it this way: LFU cares about how many times something was used, while LRU (its cousin problem) only cares about when it was last used. LFU is essentially "LRU, but frequency comes first."

2. Examples

Example 1: capacity = 2

Example 2: capacity = 3

3. Brute Force Approach

Intuition

The simplest way to track everything is to keep a dynamic array (or vector) of objects holding the key, value, frequency, and a timestamp for every element. When an eviction is needed, we scan the entire array to find the element with the minimum frequency and oldest timestamp.

Data Structures Used

• A structure Item { int key, value, freq, time; }.
• std::vector<Item> to store the cache contents.
• A global timer integer to simulate timestamps.

Algorithm

1. get(key): Iterate through the vector. If found, update freq++, time = ++timer, and return value. Otherwise, return -1.
2. put(key, value): Iterate through the vector. If found, update value, freq++, and time = ++timer. If not found:
   • If size == capacity: Scan the whole vector to find the item with the minimum freq. If multiple exist, pick the one with the smallest time. Erase it.
   • Push new Item(key, value, 1, ++timer) to the vector.

Step-by-step Dry Run

• put(1,1): Vector: [{k:1, v:1, f:1, t:1}]
• put(2,2): Vector: [{1,1,1,1}, {2,2,1,2}]
• get(1): Found 1. Update. Vector: [{1,1,2,3}, {2,2,1,2}]. Returns 1.
• put(3,3): Cap full (2). Scan vector. Min freq is 1 (Key 2). Erase Key 2. Insert Key 3. Vector: [{1,1,2,3}, {3,3,1,4}].

C++ Implementation

#include <vector>
#include <climits>
using namespace std; // Import standard namespace

// Structure to represent each cache item
struct Item {
    int key;   // The key of the cache entry
    int val;   // The value stored
    int freq;  // Frequency of access (how many times accessed)
    int time;  // Timestamp to track recency (used for tie-breaking)
};

class LFUCacheBrute {
    int capacity;        // Maximum number of items cache can hold
    int timer;           // Global timer to track recency
    vector<Item> cache;  // Vector to store cache items

public:
    // Constructor initializes capacity and timer
    LFUCacheBrute(int cap) : capacity(cap), timer(0) {}

    // Get value for a given key
    int get(int key) {
        // Iterate through cache to find the key
        for (auto& item : cache) {
            if (item.key == key) {
                item.freq++;        // Increase frequency since accessed
                item.time = ++timer; // Update timestamp to mark recent use
                return item.val;    // Return the stored value
            }
        }
        return -1; // Key not found
    }

    // Put a key-value pair into the cache
    void put(int key, int value) {
        if (capacity == 0) return; // If capacity is 0, do nothing

        // Check if key already exists in cache
        for (auto& item : cache) {
            if (item.key == key) {
                item.val = value;   // Update value
                item.freq++;        // Increase frequency
                item.time = ++timer; // Update timestamp
                return;
            }
        }

        // If cache is full, evict least frequently used item
        if (cache.size() == capacity) {
            int minFreq = INT_MAX;     // Track minimum frequency
            int oldestTime = INT_MAX;  // Track oldest timestamp for tie-breaking
            int evictIdx = -1;         // Index of item to evict

            // Find item with lowest frequency (and oldest if tie)
            for (int i = 0; i < cache.size(); i++) {
                if (cache[i].freq < minFreq || 
                   (cache[i].freq == minFreq && cache[i].time < oldestTime)) {
                    minFreq = cache[i].freq;
                    oldestTime = cache[i].time;
                    evictIdx = i;
                }
            }
            // Remove the chosen item
            cache.erase(cache.begin() + evictIdx);
        }

        // Insert new item with frequency = 1 and updated timestamp
        cache.push_back({key, value, 1, ++timer});
    }
};

Time Complexity

• get(): $O(N)$ — Linear scan.
• put(): $O(N)$ — Linear scan to find element, plus $O(N)$ to find the eviction candidate and $O(N)$ to erase from the vector. Overall $O(N)$.

Space Complexity

• $O(N)$ where $N$ is the capacity of the cache.

Why this approach is inefficient

Every operation scales linearly with the cache capacity. For a high-performance system serving millions of requests, $O(N)$ per operation is unacceptable.

4. Better Approach

Intuition

We can improve lookup time using a Hash Map and eviction time using a balanced Binary Search Tree (BST). By using a Red-Black tree (like std::set in C++), we can keep the elements sorted automatically by their frequency, and then by their timestamp.

Data Structures Used

• std::unordered_map<int, Node>: Maps keys to their node data for $O(1)$ lookups.
• std::set<Node>: Maintains nodes sorted by frequency (primary) and timestamp (secondary).

Algorithm

1. get(key): Check hash map. If found, remove from set, update freq and time, re-insert into set, update hash map. Return value.
2. put(key, value):
   • If key exists: Update value, remove from set, update freq/time, re-insert into set.
   • If new key: If at capacity, delete the first element in the set (set.begin()) because it represents the minimum frequency/oldest time. Remove it from the hash map. Create new node, insert into set and hash map.

Detailed Dry Run

• put(1,1): Map: {1}. Set: [(f:1, t:1, k:1)]
• put(2,2): Map: {1, 2}. Set: [(f:1, t:1, k:1), (f:1, t:2, k:2)]
• get(1): Find 1 in map. Remove from set. Freq=2, t=3. Insert to set. Set: [(f:1, t:2, k:2), (f:2, t:3, k:1)]. Returns 1.
• put(3,3): Cap full. set.begin() is (f:1, t:2, k:2). Evict Key 2. Insert Key 3. Set: [(f:1, t:4, k:3), (f:2, t:3, k:1)].

C++ Implementation

#include <unordered_map>
#include <set>

struct SetNode {
    int key, val, freq, time;
    bool operator<(const SetNode& other) const {
        if (freq == other.freq) return time < other.time;
        return freq < other.freq;
    }
};

class LFUCacheBetter {
    int capacity, timer;
    std::unordered_map<int, SetNode> keyNode;
    std::set<SetNode> bst;

public:
    LFUCacheBetter(int cap) : capacity(cap), timer(0) {}

    int get(int key) {
        if (keyNode.find(key) == keyNode.end()) return -1;
        SetNode node = keyNode[key];
        bst.erase(node);
        node.freq++;
        node.time = ++timer;
        bst.insert(node);
        keyNode[key] = node;
        return node.val;
    }

    void put(int key, int value) {
        if (capacity == 0) return;
        if (keyNode.find(key) != keyNode.end()) {
            SetNode node = keyNode[key];
            bst.erase(node);
            node.val = value;
            node.freq++;
            node.time = ++timer;
            bst.insert(node);
            keyNode[key] = node;
            return;
        }
        if (keyNode.size() == capacity) {
            auto it = bst.begin();
            keyNode.erase(it->key);
            bst.erase(it);
        }
        SetNode newNode = {key, value, 1, ++timer};
        bst.insert(newNode);
        keyNode[key] = newNode;
    }
};

Time Complexity

• get(): $O(\log N)$ — Hash map lookup is $O(1)$, but erasing and inserting into std::set takes $O(\log N)$.
• put(): $O(\log N)$ — Map operations are $O(1)$, set insertion/deletion is $O(\log N)$.

Space Complexity

• $O(N)$ for both the map and the set.

Advantages over brute force

Significantly faster for large capacities. $O(\log N)$ is highly scalable.

Remaining bottlenecks

$O(\log N)$ is great, but production caches (like those in OS, databases, or Redis) require $O(1)$ constant time operations to handle ultra-high throughput.

5. Optimal Approach

The standard $O(1)$ LFU Cache relies on grouping keys by their frequencies.

Core Intuition

Instead of ordering all elements in a single tree, we bucket them by frequency. If we have a list of items that have been accessed 1 time, a list for 2 times, etc., we can find the minimum frequency group instantly if we just track a minFreq variable.

Why two hash maps are required

1. Map 1 (key to Node): To find any node instantly in $O(1)$ time regardless of what frequency bucket it is currently in.
2. Map 2 (frequency to Doubly Linked List): To group nodes that share the exact same frequency.

Why doubly linked lists (DLL) are used

When a node's frequency increases, it must be removed from its current frequency list and appended to the next. A Doubly Linked List allows $O(1)$ node removal (since we have the node pointer directly from Map 1) and $O(1)$ insertion.

Why LRU is maintained inside each frequency list

We append new/updated nodes to the head of the DLL. Thus, the tail of the DLL represents the oldest node in that specific frequency bucket. When a tie-break is needed, we simply pop the tail of the minFreq's DLL.

Explain minFreq

A variable minFreq tracks the smallest frequency currently present in the cache. When eviction occurs, we look up Map2[minFreq] and evict its LRU node. minFreq is updated to 1 on new insertions, or incremented if the DLL representing the current minFreq becomes empty.

Data Structures Separated

• Node: Contains key, value, freq, prev, and next pointers.
• Frequency List (DLL): Contains a dummy head and tail, and a size counter. Supports $O(1)$ addFront() and removeNode().
• key -> node map (keyNode): std::unordered_map<int, Node*> maps a key to its physical memory address.
• frequency -> linked list map (freqListMap): std::unordered_map<int, List*> maps an integer frequency to its corresponding DLL.
• minFreq: Integer pointing to the lowest active frequency.

6. Algorithm

Explain get() step-by-step

1. Check if the key exists in keyNode. If not, return -1.
2. Extract the Node*.
3. Call updateFrequency(node).
4. Return the node's value.

Explain put() step-by-step

1. If capacity == 0, exit.
2. If key exists in keyNode, update its value, and call updateFrequency(node).
3. If key doesn't exist:
   • If cache size == capacity, call the eviction process.
   • Create a new Node.
   • Add node to freqListMap[1] (using insertAfterHead()).
   • Set minFreq = 1.
   • Add node to keyNode.
   • Increment cache size.

Explain removeNode()

Given a node pointer, rewire its neighbors:

node->prev->next = node->next

node->next->prev = node->prev

Decrement DLL size.

Explain insertAfterHead()

(Usually called addFront)

New node goes right after the dummy head.

node->next = head->next

node->prev = head

head->next->prev = node

head->next = node

Increment DLL size.

Explain updateFrequency()

1. Identify node's current frequency: freq = node->freq.
2. Remove node from freqListMap[freq].
3. Crucial check: If freq == minFreq AND the DLL for this freq is now empty (size == 0), increment minFreq++.
4. Increment node's frequency: node->freq++.
5. Add node to freqListMap[node->freq] at the head.

Explain eviction process

1. Find the DLL corresponding to minFreq: List* list = freqListMap[minFreq].
2. The LRU node is list->tail->prev.
3. Remove this node from the DLL.
4. Remove its key from keyNode.
5. Decrement cache size.
6. Delete the node from memory (avoid memory leaks).

7. Complete C++ Code

#include <unordered_map>
#include <iostream>
using namespace std; // Import standard namespace

// Node structure representing a key-value pair and its metadata
struct Node {
    int key, value, freq;   // Key, value, and frequency count
    Node* prev;             // Pointer to previous node in DLL
    Node* next;             // Pointer to next node in DLL
    
    // Constructor initializes key, value, and sets frequency = 1
    Node(int k, int v) : key(k), value(v), freq(1), prev(nullptr), next(nullptr) {}
};

// Doubly Linked List to maintain LRU order within the same frequency bucket
struct List {
    int size;       // Number of nodes in this list
    Node* head;     // Dummy head node
    Node* tail;     // Dummy tail node
    
    List() {
        // Initialize with dummy head and tail
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->prev = head;
        size = 0;
    }
    
    ~List() {
        delete head;
        delete tail;
    }
    
    // Add node to the front (most recently used within frequency bucket)
    void addFront(Node* node) {
        Node* nextNode = head->next;
        node->next = nextNode;
        node->prev = head;
        head->next = node;
        nextNode->prev = node;
        size++;
    }
    
    // Remove a specific node from the list
    void removeNode(Node* node) {
        Node* prevNode = node->prev;
        Node* nextNode = node->next;
        prevNode->next = nextNode;
        nextNode->prev = prevNode;
        size--;
    }
};

class LFUCache {
private:
    unordered_map<int, Node*> keyNode;       // Maps key → Node
    unordered_map<int, List*> freqListMap;   // Maps frequency → Doubly Linked List
    int maxSizeCache;                        // Maximum capacity of cache
    int minFreq;                             // Tracks minimum frequency in cache
    int curSize;                             // Current number of elements

    // Helper to upgrade node to the next frequency bucket
    void updateFrequency(Node* node) {
        int freq = node->freq;
        // Remove from current frequency list
        freqListMap[freq]->removeNode(node);
        
        // If this was the minFreq list and now empty, increment minFreq
        if (freq == minFreq && freqListMap[freq]->size == 0) {
            minFreq++;
        }
        
        // Increment frequency and add to new frequency list
        node->freq++;
        if (freqListMap.find(node->freq) == freqListMap.end()) {
            freqListMap[node->freq] = new List();
        }
        freqListMap[node->freq]->addFront(node);
    }

public:
    LFUCache(int capacity) {
        maxSizeCache = capacity;
        minFreq = 0;
        curSize = 0;
    }
    
    ~LFUCache() {
        // Free all allocated nodes and lists
        for (auto& pair : keyNode) delete pair.second;
        for (auto& pair : freqListMap) delete pair.second;
    }

    // Get value for a given key
    int get(int key) {
        if (keyNode.find(key) == keyNode.end()) {
            return -1; // Key not found
        }
        Node* node = keyNode[key];
        updateFrequency(node); // Increase frequency and move node
        return node->value;
    }

    // Put a key-value pair into the cache
    void put(int key, int value) {
        if (maxSizeCache == 0) return; // No capacity

        // If key already exists, update value and bump frequency
        if (keyNode.find(key) != keyNode.end()) {
            Node* node = keyNode[key];
            node->value = value;
            updateFrequency(node);
            return;
        }

        // Eviction logic if capacity is reached
        if (curSize == maxSizeCache) {
            List* minFreqList = freqListMap[minFreq];
            Node* lruNode = minFreqList->tail->prev; // Least recently used in minFreq bucket
            
            keyNode.erase(lruNode->key);             // Remove from key map
            minFreqList->removeNode(lruNode);        // Remove from list
            delete lruNode;                          // Free memory
            curSize--;
        }

        // Insert new node
        curSize++;
        minFreq = 1; // Reset min frequency to 1 for new elements
        Node* newNode = new Node(key, value);
        
        if (freqListMap.find(1) == freqListMap.end()) {
            freqListMap[1] = new List();
        }
        
        freqListMap[1]->addFront(newNode);
        keyNode[key] = newNode;
    }
};

8. Dry Run

Capacity = 2

Operation 1: put(1,1)

• Operation: Insert {1:1}
• Key frequencies: 1 -> f1
• minFreq: 1
• Frequency Lists: Map[1] -> [1]
• Cache contents: {1:1}
• Node movements: Node 1 added to Map[1]
• Evicted node: None
• Current answer: null

Operation 2: put(2,2)

• Operation: Insert {2:2}
• Key frequencies: 1 -> f1, 2 -> f1
• minFreq: 1
• Frequency Lists: Map[1] -> [2, 1] (2 is at head)
• Cache contents: {1:1, 2:2}
• Node movements: Node 2 added to Map[1] front
• Evicted node: None
• Current answer: null

Operation 3: get(1)

• Operation: Read Key 1
• Key frequencies: 1 -> f2, 2 -> f1
• minFreq: 1
• Frequency Lists: Map[1] -> [2], Map[2] -> [1]
• Cache contents: {1:1, 2:2}
• Node movements: 1 moved from Map[1] to Map[2]
• Evicted node: None
• Current answer: 1

Operation 4: put(3,3)

• Operation: Insert {3:3}, cap is 2
• Key frequencies: 1 -> f2, 3 -> f1
• minFreq: 1
• Frequency Lists: Map[1] -> [3], Map[2] -> [1]
• Cache contents: {1:1, 3:3}
• Node movements: Node 2 removed. Node 3 added to Map[1]
• Evicted node: Node 2 (LRU of minFreq 1)
• Current answer: null

Operation 5: get(2)

• Operation: Read Key 2
• Key frequencies: 1 -> f2, 3 -> f1
• minFreq: 1
• Frequency Lists: Map[1] -> [3], Map[2] -> [1]
• Cache contents: {1:1, 3:3}
• Node movements: None
• Evicted node: None
• Current answer: -1 (Not found)

Operation 6: get(3)

• Operation: Read Key 3
• Key frequencies: 1 -> f2, 3 -> f2
• minFreq: 2 (Map[1] became empty)
• Frequency Lists: Map[2] -> [3, 1]
• Cache contents: {1:1, 3:3}
• Node movements: 3 moved from Map[1] to Map[2]
• Evicted node: None
• Current answer: 3

Operation 7: put(4,4)

• Operation: Insert {4:4}, cap is 2
• Key frequencies: 3 -> f2, 4 -> f1
• minFreq: 1
• Frequency Lists: Map[1] -> [4], Map[2] -> [3]
• Cache contents: {3:3, 4:4}
• Node movements: Node 1 removed. Node 4 added to Map[1]
• Evicted node: Node 1 (LRU of minFreq 2)
• Current answer: null

Operation 8: get(1)

• Operation: Read Key 1
• Current answer: -1

Operation 9: get(3)

• Operation: Read Key 3
• Key frequencies: 3 -> f3, 4 -> f1
• minFreq: 1
• Frequency Lists: Map[1] -> [4], Map[3] -> [3]
• Current answer: 3

Operation 10: get(4)

• Operation: Read Key 4
• Key frequencies: 3 -> f3, 4 -> f2
• minFreq: 2 (Map[1] empty)
• Frequency Lists: Map[2] -> [4], Map[3] -> [3]
• Current answer: 4

9. Complexity Analysis

Why every operation is $O(1)$:

• Finding a node: $O(1)$ via keyNode hash map.
• Deleting a node from current frequency: $O(1)$ because we have the direct memory address of the node and it lives in a doubly linked list.
• Adding to the next frequency list: $O(1)$ by injecting right behind the head of the DLL.
• Eviction: $O(1)$ because minFreq instantly points to the correct DLL, and its tail->prev instantly gives the LRU element to delete.

10. Visualization

Visualizing how node promotion works via DLLs.

Initial State (Key A freq 1, Key B freq 1):

11. Interview Tips

• Common Mistakes: Forgetting to update minFreq when a node's frequency increments and it was the only node in the minFreq list. (Check if (freq == minFreq && freqListMap[freq]->size == 0) minFreq++;).
• Edge Cases: Forgetting to handle capacity == 0 right at the start of put(). This will cause segmentation faults.
• Why LRU alone fails: LRU favors recency. An item hit 1000 times a minute ago would be evicted in favor of an item hit 1 time a second ago. LFU prevents this by locking high-value items into higher frequency buckets.
• Why LFU alone needs LRU: If multiple items have a frequency of 1, and the cache is full, LFU doesn't know which one to pick. You must fall back to LRU to break the tie.
• Frequently asked interview questions: "Can you optimize space?" (You can merge the DLL implementation directly into an array if memory fragmentation is a strict concern, though Hash Map + Pointers is standard).

12. Comparison Table

13. Important Edge Cases

• capacity = 0: Cache size is zero. Every put should do nothing, every get should return -1. Guard against this at the very top of put().
• Repeated get(): A key accessed heavily will march up the frequency lists map (e.g., Map[100], Map[101]). This creates new DLLs dynamically.
• Updating existing key: When calling put() on an existing key, it should NOT reset the frequency to 1. It acts like a get() (increases frequency) but also overwrites the stored value.
• Frequency overflow discussion: In reality, an integer freq might overflow if a key is hit billions of times. In production systems (like Redis's LFU implementation), frequency is usually capped (e.g., at 255 using an 8-bit counter) or decays over time to prevent stagnant keys from permanently hogging the cache.
• Evicting when multiple keys have same frequency: Fully handled by the DLL structure. The element closest to the tail is implicitly the LRU.

14. Final Summary

• Main Intuition: To achieve $O(1)$ performance, we group cache items into buckets (Doubly Linked Lists) based on their access frequency.
• Data Structures: We bind everything together using two maps: one mapping the key to its physical Node* (for instant lookups), and another mapping a frequency integer to a DLL of nodes (to handle ties using LRU).
• Algorithm: get bumps the item to the next frequency bucket. put inserts at frequency 1 (resetting minFreq to 1). If full, put pops the tail of the minFreq DLL before inserting.
• Complexity: Time $O(1)$ for all core operations. Space $O(N)$ where $N$ is the capacity.
• Interview Takeaway: Mastery of this problem demonstrates a deep understanding of combining multiple fundamental data structures (Hash Maps + DLLs) to solve complex architectural bottlenecks. Nail the pointer rewiring and the minFreq edge case, and you will ace the interview.

code link:

https://leetcode.com/problems/lfu-cache/