LRU Cache

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

An LRU cache evicts the least recently used item when the cache reaches its capacity. "Recently used" means either read (get) or written (put).

Operations

Implement the LRUCache class:

• LRUCache(int capacity) — Initialize the cache with a positive capacity.
• int get(int key) — Return the value of the key if it exists, otherwise return -1. Accessing a key marks it as recently used.
• void put(int key, int value) — Insert or update the key-value pair. If the cache is at capacity before inserting a new key, evict the least recently used key first.

Both get and put must run in O(1) average time complexity.

Input / Output Format

You will receive a list of operations and their arguments:

• ["LRUCache", "put", "put", "get", ...]
• [[capacity], [key, val], [key, val], [key], ...]

Return a list of results corresponding to each operation. The constructor (LRUCache) returns null.

Example 1

Input:

ops    = ["LRUCache","put","put","get","put","get","put","get","get","get"]
args   = [[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]

Explanation:

1. Cache capacity = 2.
2. put(1,1) → cache: {1:1}
3. put(2,2) → cache: {1:1, 2:2}
4. get(1) → returns 1; key 1 is now most recently used.
5. put(3,3) → capacity exceeded, evict LRU key (key 2); cache: {1:1, 3:3}
6. get(2) → returns -1 (evicted)
7. put(4,4) → evict LRU key (1); cache: {3:3, 4:4}
8. get(1) → -1, get(3) → 3, get(4) → 4

Approach Hints

• A plain hash map gives O(1) lookups but can't efficiently track usage order.
• A doubly linked list maintains order and allows O(1) removal/insertion at both ends.
• Combine both: use a hash map that maps keys to nodes in the doubly linked list. The list head = most recently used, tail = least recently used.