LRU Cache

Medium#146dummy head

Design a cache for at most capacity keys. get(key) returns the key's value, or -1 if it is not there. put(key, value) adds the key or replaces its value; if that makes too many keys, the key used longest ago is dropped. Both have to run in O(1). Our calls, capacity 2: put(4, 40), put(7, 70), put(4, 45), put(9, 90), get(7), get(4) — get(7) returns -1, get(4) returns 45.

146 LRU CacheWalkthrough · 1×

Example: capacity 2; put(4, 40), put(7, 70), put(4, 45), put(9, 90), get(7), get(4). A node shows key:value.

map—capacity 2
in the listnodeout of the list for nowdropped

LRUCache(2): a cache for at most 2 keys

01/56
restart · back · play · step
Speed
1class LRUCache:
2 function init(capacity):
3 map = empty map // key → node
4 head = new node; tail = new node
5 head.next = tail; tail.prev = head
6 function get(key):
7 if key not in map:
8 return -1
9 node = map[key]
10 unlink(node)
11 addFront(node)
12 return node.val
13 function put(key, val):
14 if key in map: unlink(map[key])
15 node = new node(key, val)
16 map[key] = node
17 addFront(node)
18 if len(map) > capacity:
19 node = tail.prev
20 unlink(node)
21 remove node.key from map
22 function unlink(node):
23 node.prev.next = node.next
24 node.next.prev = node.prev
25 function addFront(node):
26 node.prev = head; node.next = head.next
27 head.next.prev = node; head.next = node
state
key
–
node
–
map
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The list is kept in order of use: every get and put moves its node right after head, so the node right before tail is always the one used longest ago.
  2. The map gives a key's node in one step, and prev links let a node be taken out of the middle with two assignments. Nothing is searched, so get and put are O(1).
  3. head and tail are dummies: a node always has neighbours on both sides, so taking out the only node or adding to an empty list needs no special case.

Complexity

Time O(1) per get and put: one map lookup and a fixed number of links. Memory O(capacity): a node and a map entry per key.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.