LRU Cache

The key idea

Pair a hash map (key to node, for O(1) lookup) with a doubly-linked list ordered by recency (head = most recent, tail = least recent). Every get and put moves the touched node to the head; eviction removes the tail. The two structures together give O(1) for both operations.

Problem

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

Implement the LRUCache class:

- LRUCache(int capacity) initializes the LRU cache with positive size capacity.
- int get(int key) returns the value of the key if the key exists, otherwise returns -1.
- void put(int key, int value) updates the value of the key if the key exists. Otherwise, adds the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put.

Examples

Input: ["LRUCache","put","put","get","put","get","put","get","get","get"] [[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]

Input: ["LRUCache","put","put","get","put","get"] [[2],[1,10],[2,20],[1],[3,30],[2]] Output: [null,null,null,10,null,-1]

Complexity

Time: O(1) Space: O(capacity)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →