Implement LFU using LRU

Source: Dev.to

📌 Core Idea

LFU (Least Frequently Used) means:

• Remove the least frequently used key.
• If multiple keys have the same frequency → remove the least recently used (LRU) among them.

📦 Data Structures Used

• key → node (for O(1) access)
• freq → doubly linked list (group nodes by frequency)
• minFreq (track the minimum frequency in the cache)

🧱 Structure Visualization

Freq = 1 → [ most recent … least recent ]
Freq = 2 → [ most recent … least recent ]
Freq = 3 → [ most recent … least recent ]

Each frequency has its own LRU list.

🚀 Example Walkthrough

Capacity = 2

1. put(1,10)

   • Freq 1: [1]
   • minFreq = 1

2. put(2,20)

3. get(1) → access key 1

   • Increase its frequency: 1 → 2
   • Freq 1: [2] Freq 2: [1]
   • minFreq = 1

4. put(3,30) (cache full)

   • minFreq = 1 → evict LRU in freq 1 (2)
   • After insertion:
     • Freq 1: [3] Freq 2: [1]
     • minFreq = 1

5. get(3) → move 3 from freq 1 → freq 2

   • Freq 1: [] Freq 2: [3, 1]
   • minFreq = 2 (freq 1 is empty)

6. put(4,40) (cache full)

   • minFreq = 2 → evict LRU in freq 2 (1)
   • After insertion:
     • Freq 1: [4] Freq 2: [3]
     • minFreq = 1

🔥 Key Observations

1. Why multiple lists?
   Different frequencies cannot be kept in a single list; each frequency maintains its own LRU order.

2. Why minFreq?
   It lets us locate the list to evict from in O(1).

3. Why doubly linked list?
   Enables O(1) removal while preserving LRU order within the same frequency.

🧠 Mental Model

Think of LFU like books on shelves:

• Shelf 1 → least used books
• Shelf 2 → moderately used books
• Shelf 3 → most used books

When removing, pick the least‑used shelf and discard the oldest book from that shelf.

🧩 Mapping to Code

🚨 Common Mistake

When a frequency list becomes empty, you must update minFreq:

if (freq == minFreq && list->size == 0)
    minFreq++;

Failing to update minFreq breaks eviction.

Code

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

    class List {
    public:
        Node* head;
        Node* tail;
        int size;
        List() : size(0) {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head->next = tail;
            tail->prev = head;
        }
        void addFront(Node* node) {
            Node* nxt = head->next;
            node->next = nxt;
            node->prev = head;
            head->next = node;
            nxt->prev = node;
            ++size;
        }
        void removeNode(Node* node) {
            Node* prv = node->prev;
            Node* nxt = node->next;
            prv->next = nxt;
            nxt->prev = prv;
            --size;
        }
    };

    int cap;
    int minFreq;
    unordered_map keyNode;   // key → node
    unordered_map freqList;  // freq → DLL

    LFUCache(int capacity) : cap(capacity), minFreq(0) {}

    void updateFreq(Node* node) {
        int f = node->freq;
        freqList[f]->removeNode(node);
        if (f == minFreq && freqList[f]->size == 0)
            ++minFreq;

        ++node->freq;
        if (!freqList.count(node->freq))
            freqList[node->freq] = new List();
        freqList[node->freq]->addFront(node);
    }

    int get(int key) {
        if (!keyNode.count(key)) return -1;
        Node* node = keyNode[key];
        updateFreq(node);
        return node->val;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (keyNode.count(key)) {
            Node* node = keyNode[key];
            node->val = value;
            updateFreq(node);
            return;
        }
        if (keyNode.size() == cap) {
            List* list = freqList[minFreq];
            Node* evict = list->tail->prev;
            keyNode.erase(evict->key);
            list->removeNode(evict);
        }
        Node* newNode = new Node(key, value);
        minFreq = 1;
        if (!freqList.count(1))
            freqList[1] = new List();
        freqList[1]->addFront(newNode);
        keyNode[key] = newNode;
    }
};