LeetCode Solutions Blog

LFU Cache

Number: 460

Difficulty: Hard

Paid? No

Problem Description

Design and implement a Least Frequently Used (LFU) cache that supports get and put operations in O(1) average time. Each key has a use counter (frequency), and when the cache reaches capacity, the least frequently used key is evicted. In case of ties (keys with the same frequency), the least recently used key is removed.

Key Insights

Maintain a mapping from key to its value and frequency.
Use an additional mapping from frequency to keys (maintaining the order of insertion or recent use) for quick eviction.
Keep a global minFreq variable to track the lowest frequency present in the cache.
When a key is accessed or updated, increase its frequency and relocate it in the frequency mapping.
Evictions occur by removing the oldest key from the lowest frequency bucket.

Space and Time Complexity

Time Complexity: O(1) average for both get and put. Space Complexity: O(capacity), where capacity is the maximum number of keys stored.

Solution

The solution utilizes two main data structures:

A hash map (keyToValFreq) that maps keys to a pair (value, frequency).
A second hash map (freqToKeys) mapping frequencies to an ordered list/set of keys. This data structure preserves the order in which keys were added to allow removal of the least recently used key when multiple keys share the same frequency.

A global minFreq variable is maintained to quickly identify the bucket with the least frequency. When a key is accessed or updated, the key is removed from its current frequency list and placed in the next higher frequency list. If the frequency list for the minimal frequency becomes empty, minFreq is updated.

This design guarantees that both get and put operations execute in constant time on average.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with detailed comments:

from collections import OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        # Initialize cache capacity and helper variables.
        self.capacity = capacity
        self.min_freq = 0  # Track the minimum frequency in cache.
        # Map key -> (value, frequency)
        self.key_to_val_freq = {}
        # Map frequency -> OrderedDict of keys for LRU ordering.
        self.freq_to_keys = {}

    def update_freq(self, key):
        # Increase frequency of the key since it was accessed.
        value, freq = self.key_to_val_freq[key]
        # Remove key from its current frequency list.
        self.freq_to_keys[freq].pop(key)
        # If current frequency list is empty, update min_freq if necessary.
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq += 1
        new_freq = freq + 1
        # Insert key into the list corresponding to the new frequency.
        if new_freq not in self.freq_to_keys:
            self.freq_to_keys[new_freq] = OrderedDict()
        self.freq_to_keys[new_freq][key] = None
        # Update the frequency entry for the key.
        self.key_to_val_freq[key] = (value, new_freq)

    def get(self, key: int) -> int:
        # Return -1 if the key is not present.
        if key not in self.key_to_val_freq:
            return -1
        # Update frequency due to access.
        self.update_freq(key)
        return self.key_to_val_freq[key][0]

    def put(self, key: int, value: int) -> None:
        # If capacity is zero, nothing can be added.
        if self.capacity <= 0:
            return
        if key in self.key_to_val_freq:
            # Update value and frequency if key exists.
            self.key_to_val_freq[key] = (value, self.key_to_val_freq[key][1])
            self.update_freq(key)
        else:
            # If cache is full, evict the least frequently used (and least recently used) key.
            if len(self.key_to_val_freq) >= self.capacity:
                # Remove the first key from the lowest frequency list.
                key_to_remove, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
                del self.key_to_val_freq[key_to_remove]
                if not self.freq_to_keys[self.min_freq]:
                    del self.freq_to_keys[self.min_freq]
            # Insert the new key with frequency 1.
            self.key_to_val_freq[key] = (value, 1)
            if 1 not in self.freq_to_keys:
                self.freq_to_keys[1] = OrderedDict()
            self.freq_to_keys[1][key] = None
            self.min_freq = 1  # Reset min_freq.