146. LRU Cache — DSA Atlas

146

MediumLinked Lists and Pointer ManipulationOrdered dictionary as hash map + doubly linked listHash map plus recency-ordered structure

LRU Cache

Design a data structure for a Least Recently Used (LRU) cache with a fixed capacity. get(key) returns the value if present (and marks it most recently used) or -1 otherwise. put(key, value) inserts or updates the key; if this exceeds capacity, evict the least recently used key. Both operations must run in O(1) average time.

Open official problem prompt ↗

In plain English

Support constant-time get and put while always evicting the item that has gone longest without use.

Picture it like this

A stack of papers on a desk: whenever you use one you move it to the top; when the desk overflows you toss the bottom paper, which is the one you touched least recently.

Example

Input: LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output: [1, -1, -1, 3, 4]
Why: put(3,3) evicts key 2 (least recently used), and put(4,4) evicts key 1, so get(2) and get(1) return -1.

Constraints

1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^5At most 2 * 10^5 calls to get and put

Pattern lesson

See the pattern, then code

Hash map plus recency-ordered structure

↗

Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. A hash map gives O(1) access by key; a doubly linked list ordered by recency gives O(1) move-to-most-recent and O(1) removal of the oldest — Python's OrderedDict bundles both.

New words, made simpleKnow these before the algorithm

LRU: Least Recently Used — the eviction policy that discards the item untouched for the longest time.
OrderedDict: A dict that remembers insertion order and supports O(1) move-to-end and pop-from-front.
Eviction: Removing an entry to stay within capacity.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash map with timestamps

Eviction scan breaks the O(1) requirement.

Store a last-used counter per key and scan for the minimum on eviction.

Time O(n) evictionSpace O(n)

Best choiceHash map + doubly linked list (OrderedDict)

Meets the O(1) contract exactly.

Map keys to nodes ordered by recency; move on access, pop oldest on overflow.

Time O(1) averageSpace O(capacity)

The rule we keep true

Invariant

At all times the OrderedDict lists keys from least-recently-used (front) to most-recently-used (back), and its size never exceeds capacity.

Why this is correct

Reasoning

move_to_end keeps the access order accurate in O(1), and popitem(last=False) removes precisely the front (oldest) key, so evictions always target the true LRU entry.

The algorithm in three movesSay these aloud before coding

1Store entries in an OrderedDict where the front is least recently used and the back is most recently used

after put1,put2: {1,2}

2On get, if the key exists move it to the back and return its value, else return -1

get1 -> order {2,1}

3On put, insert/update the key and move it to the back

put3 evicts 2 -> {1,3}

4If size exceeds capacity, pop the front (oldest) item

get2 -> -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

put10

put21

get12

put33

get24

1 · Readinsert two

2 · AskOrder?

3 · Update state{1:1, 2:2}

4 · Resultcache full at capacity 2

Key takeaway

The ordered map keeps most-recently-used at the back; puts beyond capacity evict from the front.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-6Initialize
Remember capacity and hold entries in an OrderedDict.
2
Lines 8-12get
Miss returns -1; a hit is refreshed to most-recent via move_to_end.
3
Lines 14-19put
Refresh an existing key, write the value, then evict the front if we overflow.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Updating an existing key must refresh recency without growing size
Capacity 1 evicts on every distinct new key
get on a missing key returns -1 and changes nothing

Common beginner mistakes

Forgetting to move_to_end on a get, so recency ordering drifts
Evicting with last=True (removes newest) instead of last=False
Assigning the value before move_to_end on an existing key can matter — refresh first, then write, to keep the entry at the back

Check your understanding

Why does popitem(last=False) evict the correct entry?

PyPython 3 · solution.py

Optimal

1from collections import OrderedDict23class LRUCache:4    def __init__(self, capacity: int):5        self.capacity = capacity6        self.cache: OrderedDict[int, int] = OrderedDict()78    def get(self, key: int) -> int:9        if key not in self.cache:10            return -111        self.cache.move_to_end(key)12        return self.cache[key]1314    def put(self, key: int, value: int) -> None:15        if key in self.cache:16            self.cache.move_to_end(key)17        self.cache[key] = value18        if len(self.cache) > self.capacity:19            self.cache.popitem(last=False)

Time complexityO(1) average per operationOptimized

Space complexityO(capacity)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftMetaGoogle

LRU Cache

LRU Cache

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Linked Lists and Pointer Manipulation