How do you approach LRU Cache?

Use a hash map for O(1) lookup by key.

What is the time complexity of LRU Cache?

Time complexity: O(1) for both get and put. Space complexity: O(capacity).

What are common mistakes on LRU Cache?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

Sitelet https://gitgood.dev/coding/lru-cache

gitGood.dev

← Back to problems

LRU Cache

HardData Structures

Description

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

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add 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.

Note: For this problem, implement operations as a function that takes the capacity and a list of operations.

Example 1

Input: capacity = 2, operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]

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

Explanation: After put(1,1) and put(2,2), get(1) returns 1. put(3,3) evicts key 2. get(2) returns -1 (not found).

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.

LRU Cache: approach, complexity and pitfalls

A hard design problem, graded against 5 test cases (2 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

Use a hash map for O(1) lookup by key.
Use a doubly linked list to track usage order.
Most recently used at head, least recently used at tail.

The optimal approach

Show the approach: Hash Map + Doubly Linked List

Hash map stores key -> node references for O(1) access.

Doubly linked list maintains order: most recent at head, oldest at tail.

On access, move node to head. On eviction, remove from tail.

Time: O(1) for both get and put
Space: O(capacity)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.