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.

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.

More Designproblems →

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.