The O(1) requirement for both operations rules out anything that scans a list to find or reorder elements. What’s needed is a hash map for instant key lookup, combined with a structure that can move an element to the “most recently used” end and evict from the “least recently used” end in constant time — a doubly linked list, because unlike an array or a singly linked list, it lets you unlink any node in O(1) once you have a pointer to it.
Dict + List for Recency Order
Time O(n) per callSpace O(capacity)Keep values in a plain dict, and track usage order in a separate Python list (oldest at the front). This is intuitive, but reordering that list on every get — moving the accessed key to the back — requires list.remove(key), which is O(n) since it has to search for and shift elements. It fails the problem’s O(1) requirement, but it’s a useful baseline for what the linked-list design fixes.
class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache: dict[int, int] = {} self.order: list[int] = [] # oldest at index 0
def get(self, key: int) -> int: if key not in self.cache: return -1 self.order.remove(key) # O(n): scans to find key self.order.append(key) return self.cache[key]
def put(self, key: int, value: int) -> None: if key in self.cache: self.order.remove(key) # O(n) elif len(self.cache) >= self.capacity: lru_key = self.order.pop(0) # O(n): shifts the whole list del self.cache[lru_key] self.cache[key] = value self.order.append(key)Every get and put that touches the order list costs O(n) in the worst case, since list.remove and list.pop(0) both require shifting elements — this is the exact cost the doubly linked list design below eliminates.
Hash Map + Doubly Linked List
OptimalTime O(1) per callSpace O(capacity)Store each key’s node in a dict for instant lookup, and maintain a doubly linked list ordered by recency: head side is most-recently-used, tail side is least-recently-used. Two sentinel nodes (head/tail) remove the need to special-case an empty list. Every operation reduces to two primitives, both O(1) because a doubly linked node knows its own neighbors:
_remove(node)— unlink a node from wherever it currently sits._insert_front(node)— splice a node in right afterhead(marking it most recently used).
class Node: def __init__(self, key: int = 0, val: int = 0): self.key = key self.val = val self.prev: "Node | None" = None self.next: "Node | None" = None
class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache: dict[int, Node] = {} self.head = Node() # most-recently-used side self.tail = Node() # least-recently-used side self.head.next = self.tail self.tail.prev = self.head
def _remove(self, node: Node) -> None: node.prev.next = node.next node.next.prev = node.prev
def _insert_front(self, node: Node) -> None: node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node
def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self._remove(node) self._insert_front(node) # touching a key marks it most recently used 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_front(node) if len(self.cache) > self.capacity: lru = self.tail.prev # node just before the tail sentinel self._remove(lru) del self.cache[lru.key]Tracing capacity = 2 through the same operations as the example (the trace data lives in this problem folder’s data.ts) — watch how each get unlinks the touched node from the middle and pops it back in at the MRU end, and how eviction always takes the node right before the tail:
Init: an empty map plus two sentinels — head guards the most-recently-used end, tail guards the least-recently-used end, and every live node will sit between them. Rows are shown for the four keys that appear in this trace.
All five get results — 1, -1, -1, 3, 4 — match the expected output [null,null,null,1,null,-1,null,-1,3,4].
Why it’s correct: the linked list’s order always reflects recency because every get or put on an existing key removes and re-inserts it at the front, and the node right before the tail sentinel is always the one that has gone longest untouched — exactly the eviction candidate. Complexity: the hash map gives O(1) node lookup, and unlinking/splicing a doubly linked node only touches a constant number of neighbor pointers → O(1) time per operation. Space is bounded by at most capacity cached entries → O(capacity) space — this meets the problem’s O(1) requirement exactly, which is why it’s the standard answer.