LRU Cache

Medium· design· doubly linked list· hash map

Problem

Design a key-value cache with a fixed capacity. get(key) returns the value or -1, and put(key, value) inserts or updates. When a put would exceed the capacity, evict the entry that was used least recently. Both operations must run in O(1) average time.

Examples

Input: capacity = 2; put(1,1), put(2,2), get(1), put(3,3), get(2), get(3), put(4,4), get(1), get(3), get(4)

Output: [null,null,1,null,-1,3,null,-1,3,4]

put(3,3) evicts key 2 because key 1 was just read; put(4,4) then evicts key 1.

Constraints

• 1 <= capacity <= 3000
• Up to 2 * 10^5 calls to get and put

Hints & approach

Hint 1

A hash map gives O(1) lookup but no notion of recency.

Hint 2

A doubly linked list can move any node to the front and drop the tail in O(1).

Hint 3

Combine them: the map stores key -> list node.

Approachtry the hints first

Keep a doubly linked list ordered by recency with sentinel head and tail nodes, plus a hash map from key to node. On get, look up the node, unlink it and reinsert it right after head, and return its value. On put, update and move an existing node, or create a new one at the front; if the size now exceeds capacity, remove the node just before tail and delete its key from the map. Sentinels mean unlink and insert never need null checks.

Time O(1) per operation · Space O(capacity)

← PreviousCopy List with Random Pointer Next →Merge k Sorted Lists