LRU Cache

PracticeNeetCode ↗LeetCode ↗

Design a fixed-capacity Least Recently Used (LRU) cache supporting get(key) and put(key, value), both in O(1) average time. Both operations count as "using" that key; inserting past capacity evicts the least recently used entry.

Example

Key Pointers

• O(1) get and put together point to a hashmap (O(1) key lookup) combined with a doubly linked list (O(1) reordering and eviction) — neither structure alone gets both operations to O(1).
• The list stays ordered by recency: most-recently-used near one dummy sentinel, least-recently-used near the other, so eviction is just removing the LRU-side neighbor.
• Two dummy sentinel nodes (left/right) remove edge cases for inserting into or removing from an empty list.

Step-by-Step Analysis

1. Maintain a hashmap key → node plus a doubly linked list with left (LRU-side) and right (MRU-side) dummy sentinels.
2. On get(key): if present, unlink the node and re-insert it at the MRU end, then return its value; otherwise return -1.
3. On put(key, value): if the key exists, update its value and move it to the MRU end; otherwise create a new node, insert it at the MRU end, and add it to the map.
4. If size exceeds capacity after an insert, remove the node next to the left sentinel (the LRU node) from both the list and the map.

Complexity

Time: O(1) for both get and put — Space: O(capacity)

Code

class Node:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.left = Node(0, 0)
        self.right = Node(0, 0)
        self.left.next = self.right
        self.right.prev = self.left

    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert(self, node: Node) -> None:
        prev, nxt = self.right.prev, self.right
        prev.next = node
        node.prev = prev
        node.next = nxt
        nxt.prev = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._insert(node)

        if len(self.cache) > self.cap:
            lru = self.left.next
            self._remove(lru)
            del self.cache[lru.key]

Code Explanation

How the solution above works, piece by piece.

1. cache maps key → node for O(1) lookup; the doubly linked list keeps usage order. left and right are sentinel nodes, so inserting and removing never need edge cases.
2. _remove unlinks a node by connecting its neighbours to each other; _insert puts a node just before right (the most-recent end).
3. get: if present, move the node to the most-recent end and return its value; otherwise −1.
4. put: remove any old node for the key, insert a fresh one at the most-recent end, and if the size is over capacity remove left.next (the least recently used) from both the list and the map.
5. Every operation is O(1) time; space is O(capacity).

Visual Walkthrough

Running the example with capacity = 2:

Video Explanation

NeetCode — Twitch Interview Question, LeetCode 146