LFU Cache

Hard Top 250

Associated Patterns

Linked List Arrays & Hashing

Interviewed At (Company Tags)

GoogleAmazonMicrosoftMetaApple

External Reference View on LeetCode

Problem Description

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

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Associates the key with the value if the key exists. Otherwise, inserts the key-value pair. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run 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]

Constraints

1 <= capacity <= 10⁴
0 <= key <= 10⁵
0 <= value <= 10⁹
At most 2 * 10⁵ calls will be made to get and put.

Frequency Doubly Linked Lists (O(1) Design)

To achieve O(1) operations:

Maintain a hash map vals mapping keys to their value and frequency.
Maintain a hash map counts mapping keys to their frequency level.
Maintain a hash map lists mapping frequency levels to a doubly linked list of keys. Elements in each frequency list are ordered by recency (LRU style).
Track minFreq (the overall minimum frequency in the cache). When a key is accessed:

Retrieve its current frequency f and increment it to f + 1.
Move the key from lists[f] to the head of lists[f + 1].
If lists[minFreq] is empty, increment minFreq. When inserting a new key that exceeds capacity:
Pop the tail (LRU) element from lists[minFreq].
Remove its entry from vals and counts.
Insert the new key with frequency 1 and set minFreq = 1.

Solution 1: Frequency-Mapped Doubly Linked Lists

Map frequencies to individual doubly linked lists to support O(1) frequency updates and LRU evictions.

import java.util.HashMap;
import java.util.LinkedHashSet;

class LFUCache {
    private final int capacity;
    private int minFreq;
    private final HashMap<Integer, Integer> vals; // key -> value
    private final HashMap<Integer, Integer> counts; // key -> count
    private final HashMap<Integer, LinkedHashSet<Integer>> lists; // count -> list of keys

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = -1;
        this.vals = new HashMap<>();
        this.counts = new HashMap<>();
        this.lists = new HashMap<>();
        this.lists.put(1, new LinkedHashSet<>());
    }

    public int get(int key) {
        if (!vals.containsKey(key)) return -1;
        int count = counts.get(key);
        counts.put(key, count + 1);
        lists.get(count).remove(key); // remove from current frequency list

        if (count == minFreq && lists.get(count).isEmpty()) {
            minFreq++; // increment minFreq if this level is empty
        }

        lists.putIfAbsent(count + 1, new LinkedHashSet<>());
        lists.get(count + 1).add(key); // add to next frequency list
        return vals.get(key);
    }

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

        if (vals.containsKey(key)) {
            vals.put(key, value);
            get(key); // update frequency
            return;
        }

        if (vals.size() >= capacity) {
            // Evict the least frequently used key (first element of minFreq list)
            int evict = lists.get(minFreq).iterator().next();
            lists.get(minFreq).remove(evict);
            vals.remove(evict);
            counts.remove(evict);
        }

        vals.put(key, value);
        counts.put(key, 1);
        minFreq = 1;
        lists.get(1).add(key);
    }
}

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.vals = {}  # key -> value
        self.counts = {}  # key -> count
        self.lists = defaultdict(OrderedDict)  # count -> ordered list of keys

    def get(self, key: int) -> int:
        if key not in self.vals:
            return -1
        count = self.counts[key]
        self.counts[key] = count + 1
        
        # Remove from current frequency list
        del self.lists[count][key]
        
        if count == self.min_freq and not self.lists[count]:
            self.min_freq += 1
            
        self.lists[count + 1][key] = None
        return self.vals[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
            
        if key in self.vals:
            self.vals[key] = value
            self.get(key)  # update frequency
            return
            
        if len(self.vals) >= self.capacity:
            # Evict least frequently used key
            evict_key, _ = self.lists[self.min_freq].popitem(last=False)
            del self.vals[evict_key]
            del self.counts[evict_key]
            
        self.vals[key] = value
        self.counts[key] = 1
        self.min_freq = 1
        self.lists[1][key] = None

#include <unordered_map>
#include <list>
#include <utility>

class LFUCache {
private:
    int capacity;
    int minFreq;
    std::unordered_map<int, std::pair<int, int>> vals; // key -> {value, count}
    std::unordered_map<int, std::list<int>::iterator> iterators; // key -> iterator in frequency list
    std::unordered_map<int, std::list<int>> lists; // count -> list of keys

    void updateFreq(int key) {
        int count = vals[key].second;
        vals[key].second++;
        lists[count].erase(iterators[key]); // remove from current frequency list

        if (count == minFreq && lists[count].empty()) {
            minFreq++;
        }

        lists[count + 1].push_front(key); // add to next frequency list
        iterators[key] = lists[count + 1].begin();
    }

public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        minFreq = 0;
    }

    int get(int key) {
        if (vals.find(key) == vals.end()) return -1;
        updateFreq(key);
        return vals[key].first;
    }

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

        if (vals.find(key) != vals.end()) {
            vals[key].first = value;
            updateFreq(key);
            return;
        }

        if (vals.size() >= capacity) {
            // Evict the least frequently used key (last element of minFreq list)
            int evict = lists[minFreq].back();
            lists[minFreq].pop_back();
            vals.erase(evict);
            iterators.erase(evict);
        }

        vals[key] = {value, 1};
        lists[1].push_front(key);
        iterators[key] = lists[1].begin();
        minFreq = 1;
    }
};

Complexity Analysis

Time Complexity: O(1) for get and put since all operations (list insertions, popping, map lookups) are resolved in constant time.
Space Complexity: O(capacity) auxiliary space to store values and tracking nodes.

Where It Breaks

If the LFU cache uses dynamic weights per query instead of incrementing by 1 (e.g. some resources have weight 10), moving keys between lists requires jumping arbitrary levels, making list structures harder to maintain in O(1) without heaps.

Common Mistakes

Incorrect check conditions: Forgetting to update minFreq when the current minimum frequency list becomes empty.
Using list sizes for capacity: Checking capacity limits inside the helper get method, which corrupts the insert/overwrite boundaries.