LRU Cache Implementation

Difficulty: Medium · Topics: Design, HashMap, Doubly Linked List

Difficulty: Medium | Tags: Design, HashMap, Doubly Linked List

Description

Design a data structure that follows the Least Recently Used (LRU) cache eviction policy.

Implement LRUCache with:

LRUCache(capacity) — Initialize with positive capacity.
get(key) → Return value if key exists (mark as recently used), else return -1.
put(key, value) — Update or insert. If capacity is exceeded, evict the least recently used key.

Both operations must run in O(1) time.

Examples

LRUCache cache = new LRUCache(2);

cache.put(1, 1);            // cache: {1=1}
cache.put(2, 2);            // cache: {1=1, 2=2}
cache.get(1);               // returns 1, cache: {2=2, 1=1}
cache.put(3, 3);            // evicts key 2, cache: {1=1, 3=3}
cache.get(2);               // returns -1 (not found)
cache.put(4, 4);            // evicts key 1, cache: {3=3, 4=4}
cache.get(1);               // returns -1
cache.get(3);               // returns 3
cache.get(4);               // returns 4

Constraints

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

Hints

Hint 1

Combine a HashMap (for O(1) lookup) with a Doubly Linked List (for O(1) removal/insertion for recency tracking).

Practice this problem

Solve LRU Cache Implementation in the browser