Implement LRUCache

Design a Least Recently Used (LRU) Cache with the following operations:

1. get(key): Returns the value of the key if it exists, otherwise returns -1.
2. put(key, value): Inserts or updates a key-value pair. If the cache reaches its capacity, it removes the least recently used item before inserting a new one.

The cache must maintain a constant time complexity O(1) for both operations.

Example Inputs & Outputs

const cache = new LRUCache(2);  // Create LRUCache with capacity 2

cache.put(1, 100);
cache.put(2, 200);
console.log(cache.get(1)); // Output: 100 (1 is now most recently used)

cache.put(3, 300); // Removes key 2 (Least Recently Used - LRU)
console.log(cache.get(2)); // Output: -1 (Key 2 is removed)

cache.put(4, 400); // Removes key 1 (Least Recently Used - LRU)
console.log(cache.get(1)); // Output: -1 (Key 1 is removed)
console.log(cache.get(3)); // Output: 300
console.log(cache.get(4)); // Output: 400

Constraints & Edge Cases

• 1 ≤ capacity ≤ 10⁴
• -10⁵ ≤ key, value ≤ 10⁵
• Calls to get and put should run in O(1) time complexity.
• Edge Cases:
  • Accessing a non-existent key should return -1.
  • If cache reaches its capacity, the least recently used element must be removed.
  • Updating an existing key should mark it as recently used.