LFU Cache Implementation: Multiple Solutions and Complexity Analysis

What is an LFU Cache?

LFU (Least Frequently Used) is a cache eviction algorithm that removes the item accessed the fewest times when the cache reaches its capacity and a new entry needs to be inserted. Unlike LRU (Least Recently Used), which only considers recency, LFU tracks the frequency of access for each item. This makes it particularly suitable for workloads where some items are consistently more popular over a longer period, and a one‑time recent access shouldn’t protect a rarely‑used item from eviction.

In practice, LFU is often combined with a time‑decay factor or used alongside LRU (e.g., Redis’s LFU policy) to prevent stale items that were once hot from staying in the cache indefinitely. Pure LFU implementations can be categorised by their eviction complexity: O(n) brute‑force, O(log n) with a heap, and the optimal O(1) approach using frequency‑buckets with doubly linked lists.

Why LFU Matters

Caches are critical for performance in virtually every layer of a modern application – from CPU caches to CDN edge nodes, in‑memory databases, and web application data caching. Choosing the right eviction strategy directly impacts hit ratios, latency, and resource utilisation. LFU shines when:

• Access patterns are stable: popular items remain popular for a long time (e.g., frequently accessed product metadata, CDN assets with stable traffic).
• One‑time scans or bursts should not evict genuinely hot data (LRU would be fooled by a recent but temporary spike).
• Cache pollution resistance is required: LFU naturally filters out noise because an item must accumulate enough frequency to survive.

However, pure LFU has a downside: "cache history" – an item that was very popular in the past but is no longer used still holds a high frequency count and may never be evicted. This is why production systems often introduce time‑based decay or a hybrid LFU‑LRU approach. Understanding the implementation spectrum helps you choose and tune the right variant for your specific constraints.

How an LFU Cache Works

An LFU cache must support two primary operations efficiently:

• get(key) – retrieve the value associated with the key, and increment its access frequency. Return the value (or -1 / None if missing).
• put(key, value) – insert or update the key. If the cache is at capacity and the key is new, evict the least frequently used item, then insert the new item with frequency 1. If the key already exists, update its value and increment its frequency (without affecting the eviction order until the next put).

The challenge is to locate the minimum‑frequency item (or items) for eviction without scanning the entire cache. The solutions below show three distinct strategies, each with different complexity trade‑offs.

Solution 1: Basic O(n) Brute‑Force Eviction

The simplest implementation stores all entries in a dictionary and, during eviction, iterates over the whole dictionary to find the item with the smallest frequency (and possibly the oldest among ties). This is easy to understand and works well for small caches or learning purposes, but put becomes O(n) in the worst case.

Code Example

class LFUCacheBruteForce:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}          # key -> (value, frequency)
        self.usage = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        value, freq = self.cache[key]
        self.cache[key] = (value, freq + 1)
        return value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.cache:
            # Update value and increase frequency
            _, freq = self.cache[key]
            self.cache[key] = (value, freq + 1)
            return
        # Evict if full
        if len(self.cache) >= self.capacity:
            evict_key = min(self.cache.items(),
                            key=lambda item: (item[1][1], self.usage - item[1][0]))[0]
            del self.cache[evict_key]
        # Insert new item with frequency 1
        self.cache[key] = (value, 1)
        self.usage += 1  # naive tie‑breaker: track insertion order

Complexity: get is O(1) average. put is O(n) during eviction because of min() over all items. Space complexity is O(n) for the stored entries.

Solution 2: Min‑Heap + HashMap (O(log n) Eviction)

We can improve eviction speed by maintaining a min‑heap ordered by (frequency, timestamp). Each node in the heap contains the key, frequency, and an ordinal timestamp (or a global counter). The dictionary stores the actual values and references to the heap nodes (or we keep a separate "valid" flag). When updating an existing key, we increment its frequency and push a new entry onto the heap while marking the old one as invalid. Eviction pops from the heap until a valid node is found. This gives O(log n) for both get and put.

Code Example

import heapq

class LFUCacheHeap:
    class Node:
        __slots__ = ('key', 'freq', 'time', 'valid')
        def __init__(self, key, freq, time):
            self.key = key
            self.freq = freq
            self.time = time
            self.valid = True

        def __lt__(self, other):
            # Min‑heap based on frequency, then time
            return (self.freq, self.time) < (other.freq, other.time)

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}          # key -> (value, node)
        self.heap = []           # Node instances
        self.timer = 0           # global monotonic counter

    def _touch(self, key):
        """Increment frequency and push updated node."""
        value, node = self.cache[key]
        node.valid = False          # mark old entry invalid
        new_node = self.Node(key, node.freq + 1, self.timer)
        self.timer += 1
        self.cache[key] = (value, new_node)
        heapq.heappush(self.heap, new_node)

    def _evict(self):
        """Pop invalid entries then remove the first valid."""
        while self.heap:
            node = heapq.heappop(self.heap)
            if node.valid:
                del self.cache[node.key]
                return
        # Should never be empty if capacity > 0 and cache full

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        value, _ = self.cache[key]
        self._touch(key)
        return value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.cache:
            self.cache[key] = (value, self.cache[key][1])
            self._touch(key)
            return
        # Evict if full
        if len(self.cache) >= self.capacity:
            self._evict()
        # Insert new node with frequency 1
        node = self.Node(key, 1, self.timer)
        self.timer += 1
        self.cache[key] = (value, node)
        heapq.heappush(self.heap, node)

Complexity: Both get and put involve one or two heap pushes/pops, each O(log n). The heap may contain stale nodes (up to total number of frequency increments), but in practice the number of valid entries is bounded by capacity, and stale nodes are lazily removed during eviction. This solution is a good middle ground when O(1) is not strictly required.

Solution 3: Optimal O(1) LFU – Frequency Buckets with Doubly Linked Lists

The gold standard is the O(1) time for both operations, as required by LeetCode’s 460. LFU Cache. The key insight is to maintain a frequency‑to‑bucket mapping, where each bucket is a doubly linked list of keys that share the same frequency. Additionally, we track the current minimum frequency across all buckets. When evicting, we go to the bucket for min_freq, remove the least recently added (or least recently used) item from that bucket, and then clean up if the bucket becomes empty.

The data structures used:

• Cache dictionary: key -> (value, freq, node) where node is a pointer to a linked‑list node.
• Freq map: frequency -> DoublyLinkedList of keys with that frequency.
• Min frequency tracker: integer that always points to the smallest non‑empty frequency bucket.

On get, we increment the frequency and move the key from its current frequency bucket to the next bucket (freq+1). On put, if the key exists we update the value and increment frequency (same as get). If it’s a new key and the cache is full, we evict from min_freq bucket, then insert the new key into frequency=1 bucket and reset min_freq = 1.

Detailed Code Implementation

class DLNode:
    __slots__ = ('key', 'val', 'prev', 'next')
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    """A doubly linked list with sentinel nodes for O(1) add/remove."""
    def __init__(self):
        self.head = DLNode()   # dummy head
        self.tail = DLNode()   # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_to_tail(self, node):
        """Add node just before the tail (most recently used position)."""
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node
        self.size += 1
        return node

    def remove_node(self, node):
        """Remove an arbitrary node from the list."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        self.size -= 1
        return node

    def remove_head(self):
        """Remove and return the least recently used node (head.next)."""
        if self.size == 0:
            return None
        node = self.head.next
        self.remove_node(node)
        return node

    def is_empty(self):
        return self.size == 0

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.cache = {}               # key -> (value, freq, DLNode)
        self.freq_map = {}            # freq -> DoublyLinkedList
        self.size = 0

    def _get_list(self, freq: int) -> DoublyLinkedList:
        """Return the bucket for a given frequency, creating it if absent."""
        if freq not in self.freq_map:
            self.freq_map[freq] = DoublyLinkedList()
        return self.freq_map[freq]

    def _update_freq(self, key, new_value=None):
        """Increment frequency of an existing key, optionally updating value."""
        value, freq, node = self.cache[key]
        if new_value is not None:
            value = new_value
        # Remove from current frequency bucket
        old_list = self._get_list(freq)
        old_list.remove_node(node)
        # If the bucket becomes empty and it was the min_freq, update min_freq
        if freq == self.min_freq and old_list.is_empty():
            self.min_freq += 1

        # Add to frequency+1 bucket
        new_freq = freq + 1
        new_list = self._get_list(new_freq)
        new_list.add_to_tail(node)   # keep insertion order for tie-breaking
        self.cache[key] = (value, new_freq, node)

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        value, _, _ = self.cache[key]
        self._update_freq(key)
        return value

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

        # Evict if necessary
        if self.size >= self.capacity:
            evict_list = self._get_list(self.min_freq)
            node = evict_list.remove_head()
            del self.cache[node.key]
            self.size -= 1

        # Insert new key with frequency 1
        freq = 1
        self.min_freq = 1   # reset min_freq because we are adding a new freq=1
        new_list = self._get_list(freq)
        node = DLNode(key, value)
        new_list.add_to_tail(node)
        self.cache[key] = (value, freq, node)
        self.size += 1

Important details:

• Each bucket maintains a doubly linked list where the head is the least recently added (or least recently used) among items with the same frequency. This provides a deterministic tie‑breaker.
• min_freq is only incremented when the bucket for that frequency becomes empty and we know a higher frequency bucket must exist (since the key that was removed moved to freq+1). When inserting a new key, min_freq is reset to 1 because the new key always starts at frequency 1.
• Sentinel nodes in the linked list avoid null checks and keep code clean.

Complexity Analysis Summary

Comparing the three approaches:

• Brute‑force: get O(1), put O(n). Suitable for tiny caches (capacity < 100) where code simplicity is valued.
• Min‑heap: get O(log n), put O(log n). Good when log n overhead is acceptable and you want a relatively compact implementation without full linked‑list machinery.
• Frequency buckets (O(1)): both operations strictly O(1) average time. Space O(n) for cache plus O(k) buckets where k ≤ capacity. This is the most efficient for production high‑throughput scenarios.

All solutions use O(n) space proportional to the cache capacity. The O(1) solution is the one typically expected in interviews and high‑performance caching libraries.

How to Use LFU in Practice

Many in‑memory data stores and caching libraries already provide LFU or hybrid policies:

• Redis offers the maxmemory-policy allkeys-lfu which implements a logarithmic‑counter‑based LFU with time decay to avoid cache history issues.
• Memcached doesn’t natively support LFU, but you can implement it on top of an LRU cache by maintaining external frequency counters (less efficient).
• Caffeine (Java caching library) uses a frequency‑based admission policy (TinyLFU) combined with LRU for eviction, demonstrating a modern hybrid approach.

When building a custom cache, the O(1) frequency‑bucket implementation shown above is straightforward to adapt. Just remember to define a tie‑breaking rule (LRU among same frequency) and consider whether you need time‑based expiration to prevent "old hot" items from sticking forever. You can integrate a background thread that periodically halves frequency counters, or simply add a maximum idle time on top of LFU.

Best Practices and Common Pitfalls

• Always set a capacity: An unbounded LFU cache is just a frequency map, not a cache.
• Tie‑breaking matters: Without a secondary ordering (like LRU or insertion order), eviction is non‑deterministic. The O(1) implementation above uses LRU within each bucket.
• Watch out for stale frequencies: In heap‑based LFU, invalid nodes accumulate and must be cleaned lazily. Test with high‑frequency updates to ensure the heap doesn’t grow unbounded.
• Thread safety: The basic data structures are not thread‑safe. Use locks (threading.Lock) or concurrent collections if the cache is shared across threads.
• Monitor hit ratios: Deploy with metrics to verify that LFU actually outperforms LRU for your workload. Simulate with production logs.
• Consider decay: Pure LFU can be too conservative. A simple approach is to reset frequencies when the cache is full, or use a probabilistic counter like Redis’s LFU.

Conclusion

LFU cache is a powerful eviction strategy for workloads with stable popularity distributions. Its implementation ranges from a trivial O(n) scan to a sophisticated O(1) design using frequency‑bucketed linked lists. The optimal O(1) solution is surprisingly elegant once you separate frequency tracking from item storage and use a moving minimum‑frequency pointer. By understanding the trade‑offs and building one of these implementations, you gain insight into both cache design and algorithmic efficiency that applies well beyond caching – to any system that needs to track and evict based on frequency.