146. LRU Cache
Build a fixed-size least-recently-used (LRU) cache as a class LRUCache with three members:
LRUCache(capacity)— set up an empty cache that can hold at mostcapacitykey–value pairs.get(key)— return the value stored underkey, or-1if the key is not in the cache.put(key, value)— storevalueunderkey. If the key already exists, overwrite its value. If it is a new key and the cache is already full, first throw out the entry whose last use is the oldest.
Every successful get and every put counts as a use of that key, so it becomes the most recently used entry. The goal is O(1) average time for both operations.
Example 1:
Input: LRUCache(2) · put(1,1) · put(2,2) · get(1) · put(3,3) · get(2) · put(4,4) · get(1) · get(3) · get(4)
Output: get results: 1, -1, -1, 3, 4
Explanation: With capacity 2: after put(1,1) and put(2,2), get(1) returns 1 and makes key 1 the freshest. put(3,3) must evict the stalest key, which is 2, so get(2) gives -1. put(4,4) then evicts 1, so get(1) gives -1 while get(3) and get(4) return 3 and 4.
Example 2:
Input: LRUCache(1) · put(5,7) · get(5) · put(6,8) · get(5) · get(6)
Output: get results: 7, -1, 8
Explanation: Capacity 1 means every new key evicts the previous one: put(6,8) pushes key 5 out, so the second get(5) returns -1.
Constraints:
- 1 ≤ capacity ≤ 3000
- 0 ≤ key ≤ 10⁴
- 0 ≤ value ≤ 10⁵
- 1 ≤ q ≤ 2 * 10⁵ operations, with at least one get
Hints:
A hash map alone gives O(1) lookup, but it has no idea *when* each key was last touched. You also need a structure that keeps entries in recency order and can reorder in O(1).
A doubly linked list can move any node to the front and pop the tail in O(1) — provided you can jump straight to the node. Store node references as the hash map's values, so map lookup + pointer surgery covers get, put, and eviction in constant time.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: LRUCache(2) · put(1,1) · put(2,2) · get(1) · put(3,3) · get(2) · put(4,4) · get(1) · get(3) · get(4)
Expected output: 1, -1, -1, 3, 4