244. LRU Cache — O(1) Get and Put

Medium · Design

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement `get(key)` and `put(key, value)` with O(1) time complexity each. When the cache reaches capacity, evict the least recently used item.

Examples

Example 1
Input: LRUCache(2); put(1,1); put(2,2); get(1)→1; put(3,3); get(2)→-1; get(3)→3
Output: [1,-1,3]
Explanation: After put(3,3), key 2 was LRU and evicted

Constraints

• 1 ≤ capacity ≤ 3000, 0 ≤ key, value ≤ 10⁴