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

Implement the LRUCache class with the following functionality:

LRUCache(capacity): Initializes the cache with a given positive capacity.

get(key): If the given key exists, returns its associated value; otherwise, returns -1.

put(key, value): If the key already exists, update its value. Otherwise, insert the key-value pair into the cache. If the cache exceeds its capacity due to this operation, remove the least recently used key.

Both get and put operations should have an average time complexity of O(1).

Example 1:

Input: 
["LRUCache", "put", "get", "put", "put", "get", "get", "put", "get", "get", "get"]
[[2], [2, 6], [1], [1, 5], [1, 2], [2], [1], [4, 9], [2], [1], [4]]

Output: [null, null, -1, null, null, 6, 2, null, -1, 2, 9]

Explanation:
LRUCache lRUCache = new LRUCache(2); // Initialize cache with capacity = 2
lRUCache.put(2, 6); // cache is {2=6}
lRUCache.get(1);    // returns -1 (not found)
lRUCache.put(1, 5); // cache is {2=6, 1=5}
lRUCache.put(1, 2); // update value for key=1, cache is {2=6, 1=2}
lRUCache.get(2);    // returns 6
lRUCache.get(1);    // returns 2
lRUCache.put(4, 9); // LRU max capacity is 2, LRU least recently used key was 2, evicts key 2, cache is {1=2, 4=9}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.get(1);    // returns 2
lRUCache.get(4);    // returns 9

Example 2:

Input:
["LRUCache", "put", "put", "get", "put", "get", "put", "put", "get", "get", "get"]
[[3], [1, 10], [2, 20], [1], [3, 30], [2], [4, 40], [5, 50], [3], [4], [5]]

Output: 
[null, null, null, 10, null, 20, null, null, -1, 40, 50]

Explanation:
LRUCache lRUCache = new LRUCache(3); // Initialize cache with capacity = 3
lRUCache.put(1, 10); // cache is {1=10}
lRUCache.put(2, 20); // cache is {1=10, 2=20}
lRUCache.get(1);     // returns 10
lRUCache.put(3, 30); // cache is {1=10, 2=20, 3=30}
lRUCache.get(2);     // returns 20
lRUCache.put(4, 40); // LRU max capacity is 3, LRU least recently used key was 1, evicts key 1, cache is {2=20, 3=30, 4=40}
lRUCache.put(5, 50); // LRU key was 3, evicts key 3, cache is {2=20, 4=40, 5=50}
lRUCache.get(3);     // returns -1 (not found)
lRUCache.get(4);     // returns 40
lRUCache.get(5);     // returns 50

Example 3:

Input:
["LRUCache", "put", "get", "put", "get", "get"]
[[1], [1, 100], [1], [2, 200], [1], [2]]
Output: 
[null, null, 100, null, -1, 200]
Explanation:
LRUCache lRUCache = new LRUCache(1);
lRUCache.put(1, 100); // cache is {1=100}
lRUCache.get(1);      // returns 100
lRUCache.put(2, 200); // capacity is 1, so key 1 is evicted
lRUCache.get(1);      // returns -1
lRUCache.get(2);      // returns 200

Constraints

1 <= capacity <= 3000
0 <= key <= 10⁴
0 <= value <= 10⁵
At most 2 × 10⁵ calls will be made to get and put.

88. Least Recently Used Item (LRU Cache)