LeetCode #146 Medium

LRU Cache

Fixed-capacity cache: get and put in O(1), evicting the least recently used key when full.

designhash-tabledoubly-linked-list

02

Intuition

💡

You need O(1) lookup (hash map) AND O(1) reordering by recency (doubly linked list). Marry them: map key → list node; every touch unlinks the node and reinserts at the front; eviction pops the tail. Neither structure alone can do both jobs.

03

Approach

1

Why a doubly linked list

Removing a node from the middle in O(1) needs prev and next pointers — recency order is exactly 'move to front on touch'.

2

Sentinels kill edge cases

Dummy head and tail mean every real node has real neighbours — no null checks on unlink/insert.

3

The two ops

get: look up, move node to front. put: update-or-create at front; if over capacity, unlink tail.prev and delete its map entry.

04

Solution & live demo

python

▶1class LRUCache:
▶2    def __init__(self, capacity):
▶3        self.cap = capacity
▶4        self.map = {}                      # key -> node
▶5        self.head, self.tail = Node(0, 0), Node(0, 0)
▶6        self.head.next, self.tail.prev = self.tail, self.head
▶7 
▶8    def _unlink(self, node):
▶9        node.prev.next, node.next.prev = node.next, node.prev
▶10 
▶11    def _to_front(self, node):
▶12        node.next, node.prev = self.head.next, self.head
▶13        self.head.next.prev = node
▶14        self.head.next = node
▶15 
▶16    def get(self, key):
▶17        if key not in self.map: return -1
▶18        node = self.map[key]
▶19        self._unlink(node); self._to_front(node)
▶20        return node.val
▶21 
▶22    def put(self, key, value):
▶23        if key in self.map:
▶24            self._unlink(self.map[key])
▶25        node = Node(key, value)
▶26        self.map[key] = node
▶27        self._to_front(node)
▶28        if len(self.map) > self.cap:
▶29            lru = self.tail.prev
▶30            self._unlink(lru)
▶31            del self.map[lru.key]

05

Edge cases

put on an existing key

Update value and refresh recency — must NOT evict.

capacity 1

Every distinct put evicts the previous key; sentinels keep the list sane.

06

Complexity

Time

O(1) per op

Space

O(capacity)

Map + doubly linked list in lockstep.