How do you solve LFU Cache on LeetCode?

LFU Cache (LeetCode #460) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(n) space complexity. Key insight: The LFU Cache requires careful management of both frequency and recency.

What is the brute force solution for LFU Cache?

The brute force approach for LFU Cache is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach uses a simple list to store the cache items and their frequencies. Every time we need to insert or retrieve an item, we manually check the entire list to find the least frequently used item, which can be slow. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve LFU Cache?

LFU Cache uses the following concepts: Hash Table, Linked List, Design, Doubly-Linked List. The recommended patterns to study are: Hash Map, Doubly Linked List.

What are the interview tips for LFU Cache?

Explain your thought process clearly while coding. Discuss trade-offs between different data structures you might use. Practice implementing the data structure before the interview.

What are common mistakes when solving LFU Cache?

Not handling the case when the cache is full properly. Confusing frequency with recency in the removal logic.

#460

LFU Cache

Hard

Hash TableLinked ListDesignDoubly-Linked ListHash MapDoubly Linked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(n)

💡

Intuition

Time O(1)Space O(n)

The optimal solution uses a combination of a hash map and a doubly linked list to achieve O(1) time complexity for both 'get' and 'put' operations. The hash map keeps track of the keys and their corresponding nodes in the linked list, while the linked list maintains the order of frequency.

⚙️

Algorithm

4 steps

1Step 1: Create a hash map to store key-value pairs and their frequencies.
2Step 2: Use a doubly linked list to maintain the order of keys based on their frequency.
3Step 3: For 'get', retrieve the value from the hash map, increment its frequency, and move the node in the linked list accordingly.
4Step 4: For 'put', if the key exists, update its value and frequency; if not, check if the cache is full, remove the least frequently used node, and insert the new key-value pair.

solution.py43 lines

1class Node:
2    def __init__(self, key, value):
3        self.key = key
4        self.value = value
5        self.freq = 1
6        self.prev = None
7        self.next = None
8
9class LFUCache:
10    def __init__(self, capacity: int):
11        self.capacity = capacity
12        self.min_freq = 0
13        self.key_map = {}
14        self.freq_map = collections.defaultdict(DoublyLinkedList)
15
16    def get(self, key: int) -> int:
17        if key not in self.key_map:
18            return -1
19        node = self.key_map[key]
20        self.freq_map[node.freq].remove(node)
21        if not self.freq_map[node.freq].head:
22            if node.freq == self.min_freq:
23                self.min_freq += 1
24        node.freq += 1
25        self.freq_map[node.freq].add(node)
26        return node.value
27
28    def put(self, key: int, value: int) -> None:
29        if self.capacity <= 0:
30            return
31        if key in self.key_map:
32            node = self.key_map[key]
33            node.value = value
34            self.get(key)
35            return
36        if len(self.key_map) >= self.capacity:
37            to_remove = self.freq_map[self.min_freq].remove_last()
38            del self.key_map[to_remove.key]
39        new_node = Node(key, value)
40        self.key_map[key] = new_node
41        self.freq_map[1].add(new_node)
42        self.min_freq = 1
43

ℹ

Complexity note: The optimal solution achieves O(1) time complexity for both 'get' and 'put' operations by using a hash map for quick access and a doubly linked list for maintaining frequency order. The space complexity is O(n) due to the storage of nodes and their frequencies.

1The LFU Cache requires careful management of both frequency and recency.
2Using a combination of data structures (hash map and linked list) can optimize performance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.