← all entries
A-043● Day 432026.06.18mediumleetcode #146neetcode150

LRU Cache

#hash-table#linked-list#design#doubly-linked-list
↗ leetcode #146 · lru-cache
01

Problem

· problem
P.043

LRU Cache

↗ leetcode #146

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: - LRUCache(int capacity): Initialize the LRU cache with positive size capacity. - int get(int key): Return the value of the key if the key exists, otherwise return -1. - void put(int key, int value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.

constraints
  • · 1 ≤ capacity ≤ 3000
  • · 0 ≤ key ≤ 10^4
  • · 0 ≤ value ≤ 10^5
  • · At most 2 × 10^5 calls to get() and put()
  • · Both get() and put() must achieve O(1) time complexity
// paraphrased summary — see source for full text
examples
example 1input → output
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
[null, null, null, 1, null, -1, null, -1, 3, 4]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Why must the get() operation update the cache recency order?
  • ☐
    What is the purpose of using sentinel nodes (left, right) in the doubly-linked list?
  • ☐
    Why combine a hash map with a doubly-linked list instead of using just one?
  • ☐
    Could we use only timestamps/counters to achieve O(1) performance for both operations?
  • ☐
    What happens if we update an existing key's value in put() without moving it to the right?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize cache hash map
○
self.cache = {}  # map key to node
○
self.cache = []
○
self.cache = None
○
self.cache = set()
step 2· Create sentinel nodes for list boundaries
○
self.left, self.right = Node(0, 0), Node(0, 0)
○
self.left = self.right = None
○
self.left = Node(0, 0); self.right = self.left
step 3· Disconnect node by updating both directional links
○
prev.next, nxt.prev = nxt, prev
○
prev.next = nxt
○
node.prev = None; node.next = None
○
nxt.prev = prev
step 4· Connect node at right end (most recent position)
○
node.next, node.prev = nxt, prev
○
node.next, node.prev = self.left, self.left.next
○
node.prev = self.right; node.next = None
○
prev.next = node
step 5· Get: Remove node to update recency
○
self.remove(self.cache[key])
○
return self.cache[key].val
○
self.insert(self.cache[key]); return self.cache[key].val
step 6· Put: Identify LRU node as left.next
○
lru = self.left.next
○
lru = self.right.prev
○
lru = self.cache[min(self.cache.keys())]
○
lru = list(self.cache.values())[0]
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Node:
2
    def __init__(self, key, val):
3
        self.key, self.val = key, val
4
        self.prev = self.next = None
5
6
7
class LRUCache:
8
    def __init__(self, capacity: int):
9
        self.cap = capacity
10
        self.cache = {}  # map key to node
11
12
        self.left, self.right = Node(0, 0), Node(0, 0)
13
        self.left.next, self.right.prev = self.right, self.left
14
15
    # remove node from list
16
    def remove(self, node):
17
        prev, nxt = node.prev, node.next
18
        prev.next, nxt.prev = nxt, prev
19
20
    # insert node at right
21
    def insert(self, node):
22
        prev, nxt = self.right.prev, self.right
23
        prev.next = nxt.prev = node
24
        node.next, node.prev = nxt, prev
25
26
    def get(self, key: int) -> int:
27
        if key in self.cache:
28
            self.remove(self.cache[key])
29
            self.insert(self.cache[key])
30
            return self.cache[key].val
31
        return -1
32
33
    def put(self, key: int, value: int) -> None:
34
        if key in self.cache:
35
            self.remove(self.cache[key])
36
        self.cache[key] = Node(key, value)
37
        self.insert(self.cache[key])
38
39
        if len(self.cache) > self.cap:
40
            # remove from the list and delete the LRU from hashmap
41
            lru = self.left.next
42
            self.remove(lru)
43
            del self.cache[lru.key]
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
→
[null, null, null, 1, null, -1, null, -1, 3, 4]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.