The problem
Design a cache that holds at most capacity key–value pairs. get(key) returns the value, or −1 if the key is absent. put(key, value) inserts or updates the pair; if that makes the cache too big, the least recently used key — the one read or written longest ago — is thrown out.
Both operations must take O(1) time on average.
Examples
- Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
- Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Constraints
- 1 ≤ capacity ≤ 3000
- 0 ≤ key ≤ 10⁴
- 0 ≤ value ≤ 10⁵
- At most 2 × 10⁵ calls.
The idea
Two needs, two structures. Finding a key fast needs a hash map. Keeping keys in order of use — and moving any key to the “just used” end in one step — needs a doubly linked list, whose nodes point both forward and back so one can be unlinked without a search.
The map takes each key to its node in the list. Every get or put unlinks the node and puts it at the most-recent end; when the cache overflows, the node at the least-recent end is removed from both. Two dummy nodes at the ends mean no step ever checks for an empty list.
- Time
- O(1) per operation
- Space
- O(capacity)
Solution · every language run against every case
class Node: def __init__(self, key=0, val=0): self.key, self.val = key, val self.prev = self.next = None class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.map = {} # key -> node # A doubly linked list in order of use: least recent after head, most recent before tail. self.head, self.tail = Node(), Node() self.head.next, self.tail.prev = self.tail, self.head def _unlink(self, node: Node) -> None: node.prev.next, node.next.prev = node.next, node.prev def _push_recent(self, node: Node) -> None: node.prev, node.next = self.tail.prev, self.tail self.tail.prev.next = node self.tail.prev = node def get(self, key: int) -> int: if key not in self.map: return -1 node = self.map[key] self._unlink(node) self._push_recent(node) # it has just been used return node.val def put(self, key: int, value: int) -> None: if key in self.map: self._unlink(self.map[key]) node = Node(key, value) self.map[key] = node self._push_recent(node) if len(self.map) > self.cap: lru = self.head.next # the least recently used self._unlink(lru) del self.map[lru.key]