Implement LFU using LRU

Posted on by — No Comments ↓

📌 Core Idea

LFU (Least Frequently Used) means:

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

📦 Data Structures Used

We maintain:

  • key → node (for O(1) access)
  • freq → doubly linked list (group nodes by frequency)
  • minFreq (track minimum frequency in 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

Step 1: put(1,10)

Freq 1: [1]

minFreq = 1

Step 2: put(2,20)

Freq 1: 2, 1

minFreq = 1

Step 3: get(1)

  • Access key 1
  • Increase its frequency: 1 → 2

Freq 1: [2]

Freq 2: [1]

minFreq = 1

👉 We removed 1 from freq 1 and added to freq 2

Step 4: put(3,30)

Cache is FULL → eviction needed

  • minFreq = 1
  • Look at Freq 1 → [2]

👉 Remove 2

After insertion:

Freq 1: [3]

Freq 2: [1]

minFreq = 1

Step 5: get(3)

  • Move 3 from freq 1 → freq 2

Freq 1: []

Freq 2: [3, 1]

minFreq = 2 (freq 1 is empty now)

Step 6: put(4,40)

Cache full → eviction

  • minFreq = 2
  • Freq 2 → [3, 1]

👉 Remove LRU → 1

After insertion:

Freq 1: [4]

Freq 2: [3]

minFreq = 1

🔥 Key Observations

1. Why multiple lists?

  • Different frequencies → cannot maintain in single list
  • Each frequency maintains its own LRU order

2. Why minFreq?

  • Helps directly find which list to evict from in O(1)

3. Why doubly linked list?

  • O(1) removal
  • Maintain LRU order inside same frequency

🧠 Mental Model

Think of LFU like books:

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

When removing:

  1. Pick least used shelf
  2. Remove oldest book from that shelf

🧩 Mapping to Code

Concept Code
Increase frequency updateFreq(node)
Remove LRU list->tail->prev
Track minimum minFreq
Insert new node freq = 1

🚨 Common Mistake

When a frequency list becomes empty: 

if(freq == minFreq && list is empty)
    minFreq++;

❗ If you don’t update minFreq, eviction will break

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;
        }
    };

    class List {
    public:
        Node* head;
        Node* tail;
        int size;

        List() {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head->next = tail;
            tail->prev = head;
            size = 0;
        }

        void addFront(Node* node) {
            Node* temp = head->next;
            node->next = temp;
            node->prev = head;
            head->next = node;
            temp->prev = node;
            size++;
        }

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

    int cap;
    int minFreq;

    unordered_map<int, Node*> keyNode;        // key -> node
    unordered_map<int, List*> freqList;       // freq -> DLL

    LFUCache(int capacity) {
        cap = capacity;
        minFreq = 0;
    }

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

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

        node->freq++;

        if (freqList.find(node->freq) == freqList.end()) {
            freqList[node->freq] = new List();
        }

        freqList[node->freq]->addFront(node);
    }

    int get(int key) {
        if (keyNode.find(key) == keyNode.end()) return -1;

        Node* node = keyNode[key];
        updateFreq(node);
        return node->val;
    }

    void put(int key, int value) {
        if (cap == 0) return;

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

        if (keyNode.size() == cap) {
            List* list = freqList[minFreq];
            Node* nodeToRemove = list->tail->prev;

            keyNode.erase(nodeToRemove->key);
            list->removeNode(nodeToRemove);
        }

        Node* newNode = new Node(key, value);
        minFreq = 1;

        if (freqList.find(1) == freqList.end()) {
            freqList[1] = new List();
        }

        freqList[1]->addFront(newNode);
        keyNode[key] = newNode;
    }
};

Leave a Reply