Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

LFU Cache

HARDProblemSolveExternal Links

Description

Design and implement a data structure for a Least Frequently Used (LFU) cache.

An LFU cache evicts the element that has been used the fewest number of times when the cache reaches its capacity. If there is a tie — meaning two or more elements share the same lowest usage frequency — the Least Recently Used (LRU) element among them is evicted.

Every time an element is accessed (via get or put), its usage counter increases by 1. When a new element is inserted, its usage counter starts at 1.

Implement the LFUCache class:

  • LFUCache(int capacity) — Initialize the cache with a positive capacity.
  • int get(int key) — Return the value associated with key if it exists in the cache. Otherwise, return -1. Accessing a key increases its usage frequency by 1.
  • void put(int key, int value) — Insert or update the key-value pair. If the key already exists, update its value and increase its frequency. If the key does not exist and the cache is at capacity, evict the least frequently used key (with LRU tie-breaking) before inserting the new key-value pair with frequency 1.

Both get and put must operate in O(1) average time complexity.

Examples

Example 1

Input:

["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]

Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation:

  • LFUCache(2) — Create a cache with capacity 2.
  • put(1, 1) — Insert key 1 with value 1. freq(1) = 1.
  • put(2, 2) — Insert key 2 with value 2. freq(2) = 1.
  • get(1) — Key 1 exists, return 1. freq(1) increases to 2.
  • put(3, 3) — Cache is full. We must evict the LFU key. Key 1 has freq 2, key 2 has freq 1. Key 2 is least frequent, so evict key 2. Insert key 3 with freq 1.
  • get(2) — Key 2 was evicted, return -1.
  • get(3) — Key 3 exists, return 3. freq(3) increases to 2.
  • put(4, 4) — Cache is full. Key 1 has freq 2, key 3 has freq 2. Tie! Key 1 was used less recently than key 3 (key 3 was just accessed by get), so evict key 1. Insert key 4 with freq 1.
  • get(1) — Key 1 was evicted, return -1.
  • get(3) — Key 3 exists, return 3. freq(3) increases to 3.
  • get(4) — Key 4 exists, return 4. freq(4) increases to 2.

Example 2

Input:

["LFUCache", "put", "get", "put", "get", "get"]
[[1], [2, 6], [2], [3, 9], [2], [3]]

Output: [null, null, 6, null, -1, 9]

Explanation:

  • LFUCache(1) — Capacity is just 1 element.
  • put(2, 6) — Insert key 2 with value 6. freq(2) = 1.
  • get(2) — Key 2 exists, return 6. freq(2) increases to 2.
  • put(3, 9) — Cache is full (1 element). Evict key 2 (the only key). Insert key 3. freq(3) = 1.
  • get(2) — Key 2 was evicted, return -1.
  • get(3) — Key 3 exists, return 9. freq(3) increases to 2.

Constraints

  • 1 ≤ capacity ≤ 10^4
  • 0 ≤ key ≤ 10^5
  • 0 ≤ value ≤ 10^9
  • At most 2 × 10^5 calls will be made to get and put

Editorial

Brute Force

Intuition

The most straightforward way to build an LFU cache is to store each key-value pair along with its usage frequency and a timestamp indicating when it was last accessed. We keep all entries in a simple list or array.

For get, we scan through all entries to find the key. If found, we update its frequency and timestamp, then return its value. For put, if the key already exists, we update it. If the cache is full and the key is new, we scan all entries to find the one with the lowest frequency (using the timestamp to break ties — the entry with the oldest timestamp among the lowest-frequency group is the LRU candidate). We evict that entry and insert the new one.

Think of it like a library with limited shelf space. Every book has a "times borrowed" counter. When the shelf is full and a new book arrives, the librarian checks every single book to find the one borrowed the fewest times. If two books have been borrowed equally rarely, the one that has sat untouched the longest gets removed. This manual scanning is simple but slow.

Step-by-Step Explanation

Let's trace through with capacity = 2, using a global timestamp counter:

Step 1: Initialize: entries = [], timestamp = 0.

Step 2: put(1, 1): Cache not full. Insert {key:1, val:1, freq:1, ts:1}.

  • entries = [{1:1, freq=1, ts=1}], timestamp = 1.

Step 3: put(2, 2): Cache not full. Insert {key:2, val:2, freq:1, ts:2}.

  • entries = [{1:1, freq=1, ts=1}, {2:2, freq=1, ts=2}], timestamp = 2.

Step 4: get(1): Scan entries. Found key 1. Increment freq to 2, update ts to 3. Return 1.

  • entries = [{1:1, freq=2, ts=3}, {2:2, freq=1, ts=2}], timestamp = 3.

Step 5: put(3, 3): Cache is full (2 entries). Need to evict LFU.

  • Scan: key 1 has freq=2, key 2 has freq=1. Minimum freq = 1. Only key 2 has freq=1.
  • Evict key 2. Insert {key:3, val:3, freq:1, ts:4}.
  • entries = [{1:1, freq=2, ts=3}, {3:3, freq=1, ts=4}], timestamp = 4.

Step 6: get(2): Scan entries. Key 2 not found. Return -1.

Step 7: get(3): Scan entries. Found key 3. Increment freq to 2, update ts to 5. Return 3.

  • entries = [{1:1, freq=2, ts=3}, {3:3, freq=2, ts=5}], timestamp = 5.

Step 8: put(4, 4): Cache is full. Need to evict LFU.

  • Scan: key 1 has freq=2 ts=3, key 3 has freq=2 ts=5. Both have freq=2 (tie!).
  • Tie-break by LRU: key 1 has ts=3, key 3 has ts=5. Key 1 is older → evict key 1.
  • Insert {key:4, val:4, freq:1, ts:6}.
  • entries = [{4:4, freq=1, ts=6}, {3:3, freq=2, ts=5}], timestamp = 6.

Brute Force LFU — Linear Scan for Eviction — Watch how every eviction requires scanning all entries to find the minimum frequency, with timestamp tie-breaking for LRU.

Algorithm

  1. Maintain a list of entries, each storing key, value, frequency, and timestamp.
  2. Maintain a global timestamp counter, incremented on every operation.
  3. get(key): Scan all entries for the key. If found, increment its frequency, update its timestamp, and return its value. If not found, return -1.
  4. put(key, value): If the key exists, update its value, increment frequency, update timestamp. If the key is new and cache is full:
    • Scan all entries to find the minimum frequency.
    • Among entries with that minimum frequency, find the one with the smallest (oldest) timestamp.
    • Evict that entry and replace with the new key-value pair (freq=1, timestamp=current).

Code

class LFUCache {
private:
    struct Entry {
        int key, value, freq, ts;
    };
    vector<Entry> entries;
    int capacity, timestamp;

    int findMinFreqIndex() {
        int minFreq = INT_MAX, minTs = INT_MAX, idx = -1;
        for (int i = 0; i < entries.size(); i++) {
            if (entries[i].freq < minFreq || 
                (entries[i].freq == minFreq && entries[i].ts < minTs)) {
                minFreq = entries[i].freq;
                minTs = entries[i].ts;
                idx = i;
            }
        }
        return idx;
    }

public:
    LFUCache(int capacity) : capacity(capacity), timestamp(0) {}

    int get(int key) {
        timestamp++;
        for (auto& e : entries) {
            if (e.key == key) {
                e.freq++;
                e.ts = timestamp;
                return e.value;
            }
        }
        return -1;
    }

    void put(int key, int value) {
        if (capacity == 0) return;
        timestamp++;
        for (auto& e : entries) {
            if (e.key == key) {
                e.value = value;
                e.freq++;
                e.ts = timestamp;
                return;
            }
        }
        if (entries.size() == capacity) {
            int idx = findMinFreqIndex();
            entries.erase(entries.begin() + idx);
        }
        entries.push_back({key, value, 1, timestamp});
    }
};
class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.timestamp = 0
        self.entries = []  # list of [key, value, freq, ts]

    def get(self, key: int) -> int:
        self.timestamp += 1
        for entry in self.entries:
            if entry[0] == key:
                entry[2] += 1  # increment freq
                entry[3] = self.timestamp  # update timestamp
                return entry[1]
        return -1

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        self.timestamp += 1
        for entry in self.entries:
            if entry[0] == key:
                entry[1] = value
                entry[2] += 1
                entry[3] = self.timestamp
                return
        if len(self.entries) == self.capacity:
            # Find entry with min freq, break ties by oldest ts
            min_idx = 0
            for i in range(1, len(self.entries)):
                if (self.entries[i][2] < self.entries[min_idx][2] or
                    (self.entries[i][2] == self.entries[min_idx][2] and
                     self.entries[i][3] < self.entries[min_idx][3])):
                    min_idx = i
            self.entries.pop(min_idx)
        self.entries.append([key, value, 1, self.timestamp])
import java.util.ArrayList;
import java.util.List;

class LFUCache {
    private static class Entry {
        int key, value, freq, ts;
        Entry(int k, int v, int f, int t) {
            key = k; value = v; freq = f; ts = t;
        }
    }

    private List<Entry> entries;
    private int capacity, timestamp;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.timestamp = 0;
        this.entries = new ArrayList<>();
    }

    public int get(int key) {
        timestamp++;
        for (Entry e : entries) {
            if (e.key == key) {
                e.freq++;
                e.ts = timestamp;
                return e.value;
            }
        }
        return -1;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        timestamp++;
        for (Entry e : entries) {
            if (e.key == key) {
                e.value = value;
                e.freq++;
                e.ts = timestamp;
                return;
            }
        }
        if (entries.size() == capacity) {
            int minIdx = 0;
            for (int i = 1; i < entries.size(); i++) {
                Entry cur = entries.get(i);
                Entry best = entries.get(minIdx);
                if (cur.freq < best.freq ||
                    (cur.freq == best.freq && cur.ts < best.ts)) {
                    minIdx = i;
                }
            }
            entries.remove(minIdx);
        }
        entries.add(new Entry(key, value, 1, timestamp));
    }
}

Complexity Analysis

Time Complexity: O(n) per get and put operation, where n is the capacity of the cache.

  • get: Scans all entries linearly to find the key. O(n).
  • put (eviction): Scans all entries to find the minimum frequency entry. O(n).

With up to 2 × 10^5 operations and capacity up to 10^4, the worst case is 2 × 10^9 operations — far too slow to pass the time limit.

Space Complexity: O(n)

We store at most n entries, each with constant extra metadata (frequency, timestamp).

Why This Approach Is Not Efficient

The brute force approach takes O(n) for both get and put because every operation requires scanning all entries. The two bottlenecks are:

  1. Key lookup is O(n): We scan the entire list to find a key. A hash map can reduce this to O(1).
  2. Finding the LFU entry is O(n): During eviction, we scan all entries to find the minimum frequency. We need a way to instantly identify which key has the lowest frequency.

The key insight is to separate the concerns: use a hash map for O(1) key lookup, and organize entries by frequency so we can find and remove the LFU entry in O(1). If we group all keys that share the same frequency together and maintain these groups in a structure that supports O(1) insertion and removal, we can achieve O(1) for everything.

This leads to the optimal design: a frequency map where each frequency points to a doubly linked list of keys at that frequency. Combined with a key map for O(1) lookup and a minFreq tracker, every operation becomes O(1).

Optimal Approach - Doubly Linked Lists + Hash Maps

Intuition

Imagine a building with numbered floors, where each floor represents a usage frequency. Floor 1 holds all items used exactly once, floor 2 holds items used exactly twice, and so on. Within each floor, items are lined up in order of when they were last accessed — the most recently used item is at one end, and the least recently used is at the other.

When we need to evict, we go to the lowest occupied floor and remove the item at the LRU end of that floor's line. When an item is accessed, it moves up one floor (its frequency increases by 1) and goes to the MRU end of the new floor.

This structure requires three components:

  1. keyMap — A hash map from key → node. This gives us O(1) access to any key's data (value, frequency, position in the linked list).

  2. freqMap — A hash map from frequency → doubly linked list. Each list contains all keys that currently have that frequency. Within each list, the most recently used key is near the head and the least recently used is near the tail. This gives us O(1) eviction (remove from tail of the list at minFreq) and O(1) frequency updates (remove from one list, insert at head of the next).

  3. minFreq — An integer tracking the current minimum frequency. This tells us which frequency bucket to look at during eviction, avoiding any scanning.

When a key's frequency increases from f to f+1:

  • Remove its node from the doubly linked list at freqMap[f] (O(1) with doubly linked list).
  • Insert its node at the head of freqMap[f+1] (O(1)).
  • If freqMap[f] becomes empty and f == minFreq, increment minFreq by 1.

Every operation is O(1) because each step involves only hash map lookups and doubly linked list insertions/removals — all constant time.

LFU Cache structure showing keyMap pointing to nodes organized in frequency-bucketed doubly linked lists
LFU Cache structure showing keyMap pointing to nodes organized in frequency-bucketed doubly linked lists

Step-by-Step Explanation

Let's trace through the full example with capacity = 2:

Step 1: Initialize: keyMap = {}, freqMap = {}, minFreq = 0.

Step 2: put(1, 1): Key 1 is new. Create node {key=1, val=1, freq=1}.

  • Add to keyMap: {1 → node}.
  • Add node to head of freqMap[1]: [node(1)].
  • Set minFreq = 1.
  • State: keyMap={1}, freqMap={1: [1]}, minFreq=1.

Step 3: put(2, 2): Key 2 is new. Create node {key=2, val=2, freq=1}.

  • Add to keyMap: {1 → node, 2 → node}.
  • Add node to head of freqMap[1]: [2 ↔ 1] (2 is newer/MRU, 1 is older/LRU).
  • minFreq stays 1.
  • State: keyMap={1,2}, freqMap={1: [2, 1]}, minFreq=1.

Step 4: get(1): Key 1 found in keyMap. Current freq = 1.

  • Remove node(1) from freqMap[1]. List becomes [2].
  • Increment freq to 2. Insert node(1) at head of freqMap[2]: [1].
  • freqMap[1] still has node(2), so minFreq stays 1.
  • Return value 1.
  • State: keyMap={1,2}, freqMap={1: [2], 2: [1]}, minFreq=1.

Step 5: put(3, 3): Key 3 is new, cache is full (size=2). Must evict.

  • Evict from tail of freqMap[minFreq=1]: node(2) is the tail. Remove it.
  • Remove key 2 from keyMap.
  • Create node(3) with freq=1. Add to keyMap and head of freqMap[1].
  • Set minFreq = 1 (new insertion always has freq 1).
  • State: keyMap={1,3}, freqMap={1: [3], 2: [1]}, minFreq=1.

Step 6: get(2): Key 2 not in keyMap. Return -1.

Step 7: get(3): Key 3 found. Current freq = 1.

  • Remove node(3) from freqMap[1]. List becomes empty.
  • Since freqMap[1] is empty and minFreq was 1, update minFreq = 2.
  • Increment freq to 2. Insert node(3) at head of freqMap[2]: [3, 1].
  • Return value 3.
  • State: keyMap={1,3}, freqMap={2: [3, 1]}, minFreq=2.

Step 8: put(4, 4): Key 4 is new, cache is full. Must evict.

  • Evict from tail of freqMap[minFreq=2]: node(1) is the tail (LRU among freq=2). Remove it.
  • Remove key 1 from keyMap.
  • Create node(4) with freq=1. Add to keyMap and head of freqMap[1].
  • Set minFreq = 1.
  • State: keyMap={3,4}, freqMap={1: [4], 2: [3]}, minFreq=1.

LFU Cache — O(1) Operations with Frequency Buckets — Watch how keys move between frequency buckets. Each bucket is a doubly linked list ordered by recency. Eviction always targets the tail of the minFreq bucket.

Algorithm

Data Structures:

  • keyMap: HashMap<key, Node> — maps each key to its node (which stores key, value, and frequency).
  • freqMap: HashMap<frequency, DoublyLinkedList> — maps each frequency to a DLL of nodes. Most recently used at head, least recently used at tail.
  • minFreq: integer — the current minimum frequency among all keys.

Helper — increaseFreq(node):

  1. Let f = node's current frequency.
  2. Remove node from freqMap[f].
  3. If freqMap[f] is now empty and f == minFreq, increment minFreq.
  4. Increment node's frequency to f + 1.
  5. Insert node at head of freqMap[f + 1] (creating the list if needed).

get(key):

  1. If key not in keyMap, return -1.
  2. Get node from keyMap[key].
  3. Call increaseFreq(node).
  4. Return node.value.

put(key, value):

  1. If capacity == 0, return.
  2. If key in keyMap: update node.value, call increaseFreq(node), return.
  3. If size == capacity:
    • Get the tail node from freqMap[minFreq] — this is the LFU + LRU node.
    • Remove it from freqMap[minFreq] and from keyMap.
    • Decrement size.
  4. Create new node with key, value, freq = 1.
  5. Add to keyMap[key].
  6. Insert at head of freqMap[1].
  7. Set minFreq = 1.
  8. Increment size.

Code

#include <unordered_map>
#include <list>
using namespace std;

class LFUCache {
private:
    struct Node {
        int key, value, freq;
        Node(int k, int v, int f) : key(k), value(v), freq(f) {}
    };

    int capacity, minFreq, size;
    // key -> iterator to the node in the freq list
    unordered_map<int, list<Node>::iterator> keyMap;
    // freq -> doubly linked list of nodes with that frequency
    unordered_map<int, list<Node>> freqMap;

    void increaseFreq(list<Node>::iterator it) {
        int freq = it->freq;
        int key = it->key;
        int value = it->value;

        // Remove from current frequency list
        freqMap[freq].erase(it);
        if (freqMap[freq].empty()) {
            freqMap.erase(freq);
            if (minFreq == freq) minFreq++;
        }

        // Add to next frequency list (front = MRU)
        int newFreq = freq + 1;
        freqMap[newFreq].push_front(Node(key, value, newFreq));
        keyMap[key] = freqMap[newFreq].begin();
    }

public:
    LFUCache(int capacity) : capacity(capacity), minFreq(0), size(0) {}

    int get(int key) {
        if (keyMap.find(key) == keyMap.end()) return -1;
        auto it = keyMap[key];
        int value = it->value;
        increaseFreq(it);
        return value;
    }

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

        if (keyMap.find(key) != keyMap.end()) {
            keyMap[key]->value = value;
            increaseFreq(keyMap[key]);
            return;
        }

        if (size == capacity) {
            // Evict LFU (LRU among min freq) = back of minFreq list
            auto& minList = freqMap[minFreq];
            int evictKey = minList.back().key;
            minList.pop_back();
            if (minList.empty()) freqMap.erase(minFreq);
            keyMap.erase(evictKey);
            size--;
        }

        // Insert new node with freq 1
        freqMap[1].push_front(Node(key, value, 1));
        keyMap[key] = freqMap[1].begin();
        minFreq = 1;
        size++;
    }
};
from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.min_freq = 0
        # key -> (value, freq)
        self.key_map = {}
        # freq -> OrderedDict of {key: value} (insertion order = LRU order)
        self.freq_map = defaultdict(OrderedDict)

    def _increase_freq(self, key: int) -> None:
        value, freq = self.key_map[key]
        # Remove from current frequency bucket
        del self.freq_map[freq][key]
        if not self.freq_map[freq]:
            del self.freq_map[freq]
            if self.min_freq == freq:
                self.min_freq += 1
        # Add to next frequency bucket
        new_freq = freq + 1
        self.freq_map[new_freq][key] = value
        self.key_map[key] = (value, new_freq)

    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        self._increase_freq(key)
        return self.key_map[key][0]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return

        if key in self.key_map:
            self.key_map[key] = (value, self.key_map[key][1])
            self.freq_map[self.key_map[key][1]][key] = value
            self._increase_freq(key)
            return

        if self.size == self.capacity:
            # Evict LFU (LRU among min freq)
            # popitem(last=False) removes the oldest inserted key
            evict_key, _ = self.freq_map[self.min_freq].popitem(last=False)
            if not self.freq_map[self.min_freq]:
                del self.freq_map[self.min_freq]
            del self.key_map[evict_key]
            self.size -= 1

        # Insert new key with freq 1
        self.key_map[key] = (value, 1)
        self.freq_map[1][key] = value
        self.min_freq = 1
        self.size += 1
import java.util.*;

class LFUCache {
    private int capacity, size, minFreq;
    // key -> Node
    private Map<Integer, Node> keyMap;
    // freq -> LinkedHashSet<key> (insertion order = LRU order)
    private Map<Integer, LinkedHashSet<Integer>> freqMap;
    // key -> value stored separately for clarity
    private Map<Integer, Integer> valMap;

    private static class Node {
        int freq;
        Node(int freq) { this.freq = freq; }
    }

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.minFreq = 0;
        keyMap = new HashMap<>();
        freqMap = new HashMap<>();
        valMap = new HashMap<>();
    }

    private void increaseFreq(int key) {
        Node node = keyMap.get(key);
        int freq = node.freq;

        // Remove from current frequency set
        freqMap.get(freq).remove(key);
        if (freqMap.get(freq).isEmpty()) {
            freqMap.remove(freq);
            if (minFreq == freq) minFreq++;
        }

        // Add to next frequency set
        node.freq = freq + 1;
        freqMap.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    public int get(int key) {
        if (!keyMap.containsKey(key)) return -1;
        increaseFreq(key);
        return valMap.get(key);
    }

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

        if (keyMap.containsKey(key)) {
            valMap.put(key, value);
            increaseFreq(key);
            return;
        }

        if (size == capacity) {
            // Evict LFU + LRU: first element in minFreq set
            LinkedHashSet<Integer> minSet = freqMap.get(minFreq);
            int evictKey = minSet.iterator().next();
            minSet.remove(evictKey);
            if (minSet.isEmpty()) freqMap.remove(minFreq);
            keyMap.remove(evictKey);
            valMap.remove(evictKey);
            size--;
        }

        // Insert new key with freq 1
        keyMap.put(key, new Node(1));
        valMap.put(key, value);
        freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
        size++;
    }
}

Complexity Analysis

Time Complexity: O(1) average for both get and put

  • get: One hash map lookup in keyMap to find the node (O(1)). One removal from a doubly linked list / ordered dict at the current frequency (O(1)). One insertion at the head of the next frequency's list (O(1)). One potential minFreq increment (O(1)). Total: O(1).

  • put (existing key): Same as get plus one value update. O(1).

  • put (new key, eviction): One hash map lookup to confirm key is new (O(1)). One removal from the tail of freqMap[minFreq] (O(1) in a doubly linked list). One hash map deletion (O(1)). One new node creation and insertion (O(1)). Total: O(1).

The minFreq variable is the critical piece that makes eviction O(1) — we always know exactly which frequency bucket contains the eviction candidate, without scanning.

Space Complexity: O(capacity)

We store at most capacity nodes. Each node appears in exactly one frequency bucket (a doubly linked list node) and in the keyMap. The freqMap has at most capacity entries across all buckets combined. Total auxiliary space is proportional to the number of stored keys.