How do you solve LRU Cache?

Implement the cache with a hash map for O(1) key-to-node lookup and a doubly linked list to track usage order. Define helper methods to remove a node and insert a node at the tail. On get, if the key exists, remove the node from its current position and re-insert it at the tail, then return its value. On put, if the key exists, remove the old node, then insert the new node at the tail. If capacity is exceeded, remove the head node and delete its key from the hash map. This approach guarantees O(1) time complexity for both operations.

What pattern does LRU Cache use?

The Pattern: Design & Composition (Hash Map + Doubly Linked List) The Heuristic: Combine a hash map for fast key lookup with a doubly linked list to maintain usage order, enabling O(1) access, insertion, and eviction by moving nodes to the tail on access and removing from the head on capacity overflow.

LRU Cache — System Design & Composition

Q: What is the time complexity of LRU Cache?

O(1). All operations (get, put, remove, insert) involve constant-time hash map lookups and pointer updates in the doubly linked list, ensuring O(1) time per operation.

Problem

Design a data structure that supports the operations get and put for a Least Recently Used (LRU) cache with a fixed capacity, where get returns the value of the key if it exists, otherwise -1, and put inserts or updates the value of the key, evicting the least recently used item if capacity is exceeded.

1 ≤ capacity ≤ 3000
0 ≤ key ≤ 10⁴
0 ≤ value ≤ 10⁵
At most 2 * 10⁵ calls will be made to get and put.

Example

Input:

capacity = 2
put(1, 1)
put(2, 2)
get(1)
put(3, 3)
get(2)
put(4, 4)
get(1)
get(3)
get(4)

Output: [null, null, null, 1, null, -1, null, 3, 4]

Initially, the cache is empty with capacity 2. After put(1,1) and put(2,2), the cache holds keys 1 and 2. get(1) returns 1 and marks key 1 as recently used. put(3,3) evicts key 2 (least recently used) and inserts key 3. get(2) returns -1 since key 2 was evicted. put(4,4) evicts key 1 and inserts key 4. get(1) returns -1 (evicted), get(3) returns 3, and get(4) returns 4.

Approach

Straightforward Solution

A naive approach might use a list or queue to track usage order and a hash map for values, but removing an arbitrary element from a list is O(n), making put and get operations inefficient for large caches.

Core Observation

The LRU cache requires O(1) time for both get and put operations, which demands a data structure that supports fast lookup, insertion, deletion, and ordering by recent use. A hash map provides O(1) key lookup, but does not maintain order. A doubly linked list supports O(1) insertion and removal of nodes and maintains the order of usage, enabling quick eviction of the least recently used item.

Path to Optimal

Preview

The key insight is to combine a hash map and a doubly linked list. The hash map stores keys mapped to nodes in the doubly linked list, which maintains the usage order with the most recently used at the tail and least recently used at the head…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement the cache with a hash map for O(1) key-to-node lookup and a doubly linked list to track usage order. Define helper methods to remove a node and insert a node at the tail…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1)

All operations (get, put, remove, insert) involve constant-time hash map lookups and pointer updates in the doubly linked list, ensuring O(1) time per operation.

Space

O(capacity)

The hash map and doubly linked list store at most capacity number of nodes, so space scales linearly with the cache capacity.

Solution

Python

1class Node:
  def __init__(self, key, val):
      self.key, self.val = key, val
      self.prev = self.next = None
5
6class LRUCache:
  def __init__(self, capacity: int):
      self.cap = capacity
      self.cache = {}
      self.left, self.right = Node(0, 0), Node(0, 0)
      self.left.next, self.right.prev = self.right, self.left
12
  def remove(self, node):
      prev, nxt = node.prev, node.next
      prev.next, nxt.prev = nxt, prev
16
  def insert(self, node):
      prev, nxt = self.right.prev, self.right
      prev.next = nxt.prev = node
      node.next, node.prev = nxt, prev
21
  def get(self, key: int) -> int:
      if key in self.cache:
          self.remove(self.cache[key])
          self.insert(self.cache[key])
          return self.cache[key].val
      return -1
28
  def put(self, key: int, value: int) -> None:
      if key in self.cache:
          self.remove(self.cache[key])
      self.cache[key] = Node(key, value)
      self.insert(self.cache[key])
34
      if len(self.cache) > self.cap:
          lru = self.left.next
          self.remove(lru)
          del self.cache[lru.key]

Step-by-Step Solution

1

Define Node Structure for Doubly Linked List Entries

3self.key, self.val = key, val
4self.prev = self.next = None

Objective

To represent each cache entry as a doubly linked list node storing its key, value, and neighbor pointers.

Key Insight

The cache map points to nodes, not raw values. Each node must therefore carry its key for O(1) eviction cleanup and its prev/next links for O(1) removal and insertion.

Interview Quick-Check

Core Logic

Each cache entry needs both payload fields and doubly linked list pointers so it can move in O(1).

Common Pitfalls & Bugs

If the node does not store its key, eviction cannot remove the matching map entry in O(1).

2

Initialize Cache State with Dummy Head and Tail Nodes

To set up the cache capacity, hash map, and doubly linked list with sentinel nodes to simplify insertion and removal operations.

3

Remove a Node from the Doubly Linked List

To unlink a node from its current position in the doubly linked list in O(1) time.

4

Insert a Node at the Tail to Mark as Most Recently Used

To insert a node right before the dummy tail node, marking it as the most recently used item.

5

Retrieve Value and Update Usage on Get Operation

To return the value associated with a key if it exists and update its position to the most recently used.

6

Insert or Update Key-Value Pair and Evict if Necessary on Put

To insert a new key-value pair or update an existing one, move it to the most recently used position, and evict the least recently used item if capacity is exceeded.

5 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 15 Critical

prev.next, nxt.prev = nxt, prev

Update pointers to bypass the target node, removing it from the list.

This pointer update is the critical operation that removes a node in constant time, enabling efficient cache updates without list traversal.

Line 9 Critical

self.cache = {}

Initialize the hash map to store key-node mappings.

The hash map enables O(1) lookup of nodes by key, which is essential for efficient get and put operations.

Line 19 Critical

prev.next = nxt.prev = node

Link the previous node and dummy tail to the new node.

This dual pointer assignment is essential to correctly insert the node at the tail, ensuring the list remains well-formed and the node is recognized as most recently used.

Full line-by-line criticality + rationale for all 24 lines available on Pro.

Test Your Understanding

Why does combining a hash map with a doubly linked list enable O(1) time complexity for both get and put operations in an LRU cache?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct LRU Cache from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the LRU Cache drill

or drill a free problem

1	`class Node:`
2	`def __init__(self, key, val):`
3	`self.key, self.val = key, val`
4	`self.prev = self.next = None`
5
6	`class LRUCache:`
7	`def __init__(self, capacity: int):`
8	`self.cap = capacity`
9	`self.cache = {}`
10	`self.left, self.right = Node(0, 0), Node(0, 0)`
11	`self.left.next, self.right.prev = self.right, self.left`
12
13	`def remove(self, node):`
14	`prev, nxt = node.prev, node.next`
15	`prev.next, nxt.prev = nxt, prev`
16
17	`def insert(self, node):`
18	`prev, nxt = self.right.prev, self.right`
19	`prev.next = nxt.prev = node`
20	`node.next, node.prev = nxt, prev`
21
22	`def get(self, key: int) -> int:`
23	`if key in self.cache:`
24	`self.remove(self.cache[key])`
25	`self.insert(self.cache[key])`
26	`return self.cache[key].val`
27	`return -1`
28
29	`def put(self, key: int, value: int) -> None:`
30	`if key in self.cache:`
31	`self.remove(self.cache[key])`
32	`self.cache[key] = Node(key, value)`
33	`self.insert(self.cache[key])`
34
35	`if len(self.cache) > self.cap:`
36	`lru = self.left.next`
37	`self.remove(lru)`
38	`del self.cache[lru.key]`