#146 LRU Cache
Design a fixed-capacity key-value cache with least-recently-used eviction. Implement a class with:
LRUCache(capacity), create a cache holding at mostcapacityentries.get(key), return the value stored underkey, or-1if absent.put(key, value), insert or overwritekey. If inserting a new key would exceed capacity, first evict the least recently used entry.
Both get and a successful put count as a "use" of that key, and both
operations must run in O(1) average time.
Examples
Input
ops = ["LRUCache","put","put","get","put","get","get"], args = [[2],[1,1],[2,2],[1],[3,3],[2],[3]]Output
[null, null, null, 1, null, -1, 3]Capacity 2. After get(1), key 1 is fresh, so put(3, 3) evicts key 2, the stale one. get(2) misses; get(3) hits.
Input
ops = ["LRUCache","put","put","put","get"], args = [[1],[7,1],[7,2],[7],[8,9]] then get(7)Output
put(7,2) overwrites in place; get(7) → 2; put(8,9) then evicts 7Overwriting an existing key never evicts. The size didn't grow. Eviction happens only when a genuinely new key exceeds capacity.
Constraints
1 ≤ capacity ≤ 30000 ≤ key ≤ 10⁴, 0 ≤ value ≤ 10⁵Up to 2 × 10⁵ calls to get and putget and put must be O(1) average
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.