LeetCode Solutions Blog

LFU Cache

Difficulty: Hard

Problem Description

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement the LFUCache class with the following methods:

LFUCache(int capacity): Initializes the object with the capacity of the data structure.
int get(int key): Gets the value of the key if it exists in the cache, otherwise returns -1.
void put(int key, int value): Updates the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it invalidates and removes the least frequently used key before inserting a new item.

Key Insights

The cache must track the frequency of accesses for each key.
When the cache exceeds its capacity, it must evict the least frequently used key.
In case of a tie in frequency, the least recently used key should be evicted.
Operations (get and put) should be efficient, ideally O(1) time complexity.

Space and Time Complexity

Time Complexity: O(1) for both get and put operations on average.
Space Complexity: O(capacity) for storing the keys and their associated data.

Solution

To solve the LFU Cache problem, we use a combination of:

A hash map to store the key-value pairs and their frequencies.
A second hash map (or a linked list) to store keys by their frequency for efficient removal of the least frequently used key.
A variable to track the least frequency and a mechanism to update the frequency of keys when they are accessed or modified.

The primary data structures used are:

A hash map (dictionary) for storing keys and their values along with their frequencies.
A doubly linked list to maintain the order of keys by their access frequency.

Code Solutions

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None

class DoubleLinkedList:
    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(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def pop(self):
        if self.size > 0:
            node = self.tail.prev
            self.remove(node)
            return node
        return None

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_map = {}
        self.freq_map = {}

    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        node = self.key_map[key]
        self._update(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.key_map:
            node = self.key_map[key]
            node.value = value
            self._update(node)
        else:
            if len(self.key_map) >= self.capacity:
                # Evict the least frequently used key
                lfu_list = self.freq_map[self.min_freq]
                node_to_remove = lfu_list.pop()
                del self.key_map[node_to_remove.key]
            new_node = Node(key, value)
            self.key_map[key] = new_node
            self.min_freq = 1
            if 1 not in self.freq_map:
                self.freq_map[1] = DoubleLinkedList()
            self.freq_map[1].add(new_node)

    def _update(self, node: Node) -> None:
        freq = node.freq
        self.freq_map[freq].remove(node)
        if freq == self.min_freq and self.freq_map[freq].size == 0:
            self.min_freq += 1
        node.freq += 1
        if node.freq not in self.freq_map:
            self.freq_map[node.freq] = DoubleLinkedList()
        self.freq_map[node.freq].add(node)