Loading problem…
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with a given capacity. The get method should return the value of a key if it exists and mark it as recently used, otherwise return -1. The put method should update or insert the key-value pair. If the cache exceeds its capacity, evict the least recently used key. Both operations must run in O(1) average time.
Example 1
Input: operations = ["LRUCache","put","put","get","put","get","put","get","get","get"], arguments = [[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: With capacity 2: after put(1), put(2) and get(1), key 2 is the least recently used, so put(3) evicts it and get(2) returns -1. Then key 1 is the least recently used, so put(4) evicts it. get(1) returns -1, while keys 3 and 4 are found.
Example 2
Input: operations = ["LRUCache","put","get","put","get","get"], arguments = [[1],[2,1],[2],[3,2],[2],[3]]
Output: [null,null,1,null,-1,2]
Explanation: With capacity 1, get(2) returns 1. put(3,2) evicts key 2 to make room, so get(2) returns -1 and get(3) returns 2.
Example 3
Input: operations = ["LRUCache","put","put","put","put","get","get"], arguments = [[2],[2,1],[1,1],[2,3],[4,1],[1],[2]]
Output: [null,null,null,null,null,-1,3]
Explanation: put(2,3) updates key 2 and makes it the most recently used, leaving key 1 as the least recently used. put(4,1) evicts key 1, so get(1) returns -1 and get(2) returns the updated value 3.
Build the data structure by hand to see *why* O(1) is achievable. We need (a) instant lookup by key — a hash map gives that. And (b) instant move-to-front + instant evict-from-back — a **doubly linked list** with sentinel head/tail nodes gives that. Wire them together: the hash map points at nodes, and each node knows its `prev` and `next` so it can detach itself in O(1).
Run checks all cases above. Submit evaluates all test cases.