Leetcode 460. LFU Cache

Let's trace through an example with capacity=2. Start with empty cache [].

Operation 1: put(1, 'a') → cache is now [(key:1, val:'a', freq:1)]

Operation 2: put(2, 'b') → cache is now [(1,'a',freq:1), (2,'b',freq:1)]. Cache is at capacity!

Operation 3: get(1) → returns 'a' and increases frequency → [(1,'a',freq:2), (2,'b',freq:1)]

Operation 4: put(3, 'c') → Cache is full! Must evict the least frequently used. Key 2 has freq:1 (lowest), so evict it → [(1,'a',freq:2), (3,'c',freq:1)]

Operation 5: put(1, 'd') → Key 1 already exists, update its value and increase frequency → [(1,'d',freq:3), (3,'c',freq:1)]

Key constraint: Both get and put operations must run in O(1) average time.

Edge cases: What if multiple items have the same lowest frequency? (tie-break by least recently used - evict the one that was accessed longest ago). What if we get() a non-existent key? (return -1). What if we put() an existing key? (update value AND increment frequency).

We need to track THREE pieces of information for each cache entry: the value itself, how many times it's been accessed (frequency), AND when it was last used (for tie-breaking).

The challenge is: when evicting, we need to instantly find the item with minimum frequency, and if there's a tie, the least recently used among them.

A naive approach of scanning through all items to find the minimum frequency would make every operation O(n), violating the O(1) requirement.

But if we organize items by their frequency level, we can instantly access the least-frequently-used group. Within each frequency level, we need to track access order for tie-breaking.

Think of organizing books in a library by popularity:

• Books accessed 1 time go on shelf 1 (ordered by when they were last touched)
• Books accessed 2 times go on shelf 2 (ordered by when they were last touched)
• Books accessed 3 times go on shelf 3, etc.

When removing books, always look at the lowest-numbered shelf first. Within that shelf, books are ordered by time - remove the oldest one (front of the line).

When a book is accessed, it moves up one shelf and goes to the back of the line on that new shelf. This 'grouping by frequency + ordering by recency within each group' structure makes finding the eviction candidate instant.

The optimal approach uses a combination of hash maps and doubly-linked lists to achieve O(1) operations. Maintain a hash map from keys to cache nodes (containing value and frequency), another hash map from frequency levels to doubly-linked lists of nodes at that frequency, and track the minimum frequency level. When accessing a key, move it from its current frequency list to the next frequency list. When evicting, remove the least-recently-used node from the minimum frequency list. This structure allows instant lookups, updates, and evictions.

def lfu_cache_demo(capacity, operations):
    """
    Simulate LFU cache operations with O(1) get and put.
    Uses hash maps and doubly-linked lists for optimal performance.
    """
    # Node class for doubly-linked list
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.freq = 1
            self.prev = None
            self.next = None
    
    # Doubly-linked list for each frequency level
    class DLinkedList:
        def __init__(self):
            self.head = Node(0, 0)
            self.tail = Node(0, 0)
            self.head.next = self.tail
            self.tail.prev = self.head
            self.size = 0
        
        def add_node(self, node):
            # Add node right after head (most recent)
            node.next = self.head.next
            node.prev = self.head
            self.head.next.prev = node
            self.head.next = node
            self.size += 1
        
        def remove_node(self, node):
            # Remove node from list
            node.prev.next = node.next
            node.next.prev = node.prev
            self.size -= 1
        
        def remove_tail(self):
            # Remove least recently used node (before tail)
            if self.size > 0:
                lru_node = self.tail.prev
                self.remove_node(lru_node)
                return lru_node
            return None
    
    # Initialize cache structures
    cache = {}  # key -> Node
    freq_map = {}  # frequency -> DLinkedList
    min_freq = 0
    cap = capacity
    results = []
    
    def update_freq(node):
        # Remove node from current frequency list
        freq = node.freq
        freq_map[freq].remove_node(node)
        
        # Update min_freq if current list is empty
        if freq == min_freq and freq_map[freq].size == 0:
            min_freq = freq + 1
        
        # Increment frequency and add to new list
        node.freq += 1
        new_freq = node.freq
        if new_freq not in freq_map:
            freq_map[new_freq] = DLinkedList()
        freq_map[new_freq].add_node(node)
    
    def get(key):
        # Get value and update frequency
        if key not in cache:
            return -1
        
        node = cache[key]
        update_freq(node)
        return node.value
    
    def put(key, value):
        nonlocal min_freq
        
        if cap <= 0:
            return
        
        # Update existing key
        if key in cache:
            node = cache[key]
            node.value = value
            update_freq(node)
            return
        
        # Evict if at capacity
        if len(cache) >= cap:
            # Remove LRU node from min frequency list
            lru_list = freq_map[min_freq]
            lru_node = lru_list.remove_tail()
            if lru_node:
                del cache[lru_node.key]
        
        # Insert new node
        new_node = Node(key, value)
        cache[key] = new_node
        min_freq = 1
        if 1 not in freq_map:
            freq_map[1] = DLinkedList()
        freq_map[1].add_node(new_node)
    
    # Process all operations
    for op in operations:
        op_type = op[0]
        if op_type == "put":
            key, value = op[1], op[2]
            put(key, value)
            results.append(None)
        elif op_type == "get":
            key = op[1]
            result = get(key)
            results.append(result)
    
    return results

• Multi-level hash map architecture: LFU cache requires nested hash maps - one mapping keys to values/frequencies, and another mapping each frequency level to a doubly-linked list of keys. This layered structure enables O(1) access while maintaining frequency ordering, a pattern applicable whenever you need fast lookups across multiple dimensions.
• Doubly-linked list for LRU within frequency: Within each frequency bucket, use a doubly-linked list to track recency order, allowing O(1) removal of the least-recently-used item when evicting. This combines LFU and LRU policies elegantly - the frequency determines which bucket, the list position determines which item within that bucket.
• Minimum frequency tracking optimization: Maintain a minFreq variable that only increments when the last item at that frequency is removed or promoted. This avoids scanning all frequency levels during eviction - you always know exactly which frequency bucket contains eviction candidates, ensuring true O(1) eviction time.
• Frequency promotion pitfall: When incrementing a key's frequency on access, you must remove it from the old frequency list AND add to the new frequency list in the correct order. Forgetting to update both structures or updating minFreq incorrectly (it should only reset to 1 on new insertions, not on promotions) breaks the eviction logic.
• Capacity-based eviction timing: Eviction happens before insertion when at capacity, not after. Check capacity first, evict the LRU item from the minFreq bucket, then insert the new item at frequency 1. This ensures you never exceed capacity and correctly reset minFreq to 1 for new insertions.
• Real-world caching systems: This pattern directly applies to CDN edge caching, database query caches, and browser resource management where you want to keep frequently-accessed items while still evicting stale popular items. The dual LFU+LRU policy balances long-term popularity with recent relevance better than either policy alone.