DSA problem
LRU Cache
Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement an LRUCache class with these operations: LRUCache(capacity) constructs a cache that holds at most capacity key-value pairs; get(key) returns the value if the key exists or -1 otherwise, and marks the key as most recently used; put(key, value) inserts or updates the key, marking it most recently used, and evicts the least recently used key if the cache exceeds capacity. Both operations must run in O(1) average time.
A hash map alone gives O(1) lookup but no ordering. A linked list alone gives O(1) insert/remove if you have the node pointer but O(n) lookup. The classic LRU design combines them: a hash map from key to a node in a doubly linked list, and a doubly linked list ordered by recency — most recently used at the head, least recently used at the tail. The hash map gives instant access to any node; the list gives instant reordering.
Use dummy head and tail sentinels to eliminate every null check during splice operations. Each node holds the key, the value, and prev/next pointers. The key is stored on the node (not just in the map) because eviction needs to remove the map entry for the LRU node, and you cannot get the key back from the node without storing it there.
The core helper operations are removeNode(node) (unlink from current position) and addToFront(node) (insert right after the head sentinel). get does removeNode + addToFront on a hit. put either updates and moves to front, or creates a new node, links it at the front, and — if size exceeds capacity — unlinks the tail.prev node and deletes its key from the map. Every operation touches at most a constant number of pointers, so both are truly O(1).
Examples
LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2)[1, -1]LRUCache(2); put(1,1); put(2,2); put(1,10); get(1)10LRUCache(1); put(1,1); put(2,2); get(1)-1Constraints
- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- At most 2 * 10^5 calls will be made to get and put.
- Both get and put must run in O(1) average time complexity.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.