45. LRU Cache

Medium · Linked List

Design and implement a Least Recently Used (LRU) Cache with a fixed capacity. The cache should support two operations: `get(key)` returns the value of the key if it exists, otherwise returns -1; `put(key, value)` inserts or updates the key-value pair. When the cache reaches its capacity, the least recently used item should be evicted before inserting a new item. Both `get` and `put` operations should run in O(1) time.

You will be given a sequence of operations to perform on the cache. Each operation is either `['GET', key]` or `['PUT', key, value]`. Return an array of results for each GET operation (in order), where each result is the value retrieved or -1 if not found.

Examples

Example 1
Input: capacity = 2, operations = [['PUT', 1, 1], ['PUT', 2, 2], ['GET', 1], ['PUT', 3, 3], ['GET', 2]]
Output: [1, -1]
Explanation: Cache capacity is 2. After PUT(1,1) and PUT(2,2), cache has {1:1, 2:2}. GET(1) returns 1 and marks key 1 as recently used. PUT(3,3) evicts key 2 (least recently used), cache becomes {1:1, 3:3}. GET(2) returns -1 since key 2 was evicted.
Example 2
Input: capacity = 1, operations = [['PUT', 1, 100], ['GET', 1], ['PUT', 2, 200], ['GET', 1], ['GET', 2]]
Output: [100, -1, 200]
Explanation: With capacity 1, PUT(1,100) stores {1:100}. GET(1) returns 100. PUT(2,200) evicts key 1 and stores {2:200}. GET(1) returns -1 (evicted). GET(2) returns 200.

Constraints