How do you solve LRU Cache on LeetCode?

LRU Cache (LeetCode #146) 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: Using a HashMap allows for quick access to values, while a Doubly Linked List maintains the order of usage.

What is the brute force solution for LRU Cache?

The brute force approach for LRU Cache is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves using a simple list to store the cache items. Whenever we access an item, we check if it exists in the list and move it to the front. If we exceed the capacity, we remove the last item from the list. The optimal Optimal Solution approach improves this to O(1).

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

LRU 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 LRU Cache?

Always clarify the requirements and constraints of the problem before jumping into coding. Think about the data structures that best fit the problem; in this case, consider both access speed and order maintenance. Practice explaining your thought process as you code; it helps in interviews.

What are common mistakes when solving LRU Cache?

Not maintaining the order of usage correctly when accessing or inserting items. Confusing the eviction logic, leading to incorrect cache states.

#146

LRU Cache

Medium

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 approach uses a combination of a HashMap and a Doubly Linked List. The HashMap provides O(1) access to cache items, while the Doubly Linked List maintains the order of usage, allowing for quick removal of the least recently used item.

⚙️

Algorithm

3 steps

1Step 1: Initialize a HashMap to store key-value pairs and a Doubly Linked List to maintain the order of usage.
2Step 2: For 'get', check if the key exists in the HashMap; if yes, move it to the front of the list and return its value, else return -1.
3Step 3: For 'put', check if the key exists; if yes, update its value and move it to the front. If not, add it to the front. If the list exceeds capacity, remove the last node.

solution.py48 lines

1class Node:
2    def __init__(self, key, value):
3        self.key = key
4        self.value = value
5        self.prev = None
6        self.next = None
7
8class LRUCache:
9    def __init__(self, capacity: int):
10        self.capacity = capacity
11        self.cache = {}
12        self.head = Node(0, 0)
13        self.tail = Node(0, 0)
14        self.head.next = self.tail
15        self.tail.prev = self.head
16
17    def _remove(self, node):
18        prev = node.prev
19        new = node.next
20        prev.next = new
21        new.prev = prev
22
23    def _add(self, node):
24        prev = self.head
25        next = self.head.next
26        prev.next = node
27        node.prev = prev
28        node.next = next
29        next.prev = node
30
31    def get(self, key: int) -> int:
32        if key in self.cache:
33            node = self.cache[key]
34            self._remove(node)
35            self._add(node)
36            return node.value
37        return -1
38
39    def put(self, key: int, value: int) -> None:
40        if key in self.cache:
41            self._remove(self.cache[key])
42        node = Node(key, value)
43        self.cache[key] = node
44        self._add(node)
45        if len(self.cache) > self.capacity:
46            lru = self.tail.prev
47            self._remove(lru)
48            del self.cache[lru.key]

ℹ

Complexity note: The time complexity is O(1) for both 'get' and 'put' operations due to the direct access provided by the HashMap and the efficient order maintenance by the Doubly Linked List.

1Using a HashMap allows for quick access to values, while a Doubly Linked List maintains the order of usage.
2Eviction of the least recently used item can be efficiently handled by removing the tail node of the Doubly Linked List.

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