AlgoViz
HomeStack

LRU Cache

Medium

Hash map plus a doubly linked list

Problem

Design a Least-Recently-Used cache with O(1) get and put.

In simple words

A hash map plus a doubly linked list keeps items in use-order; evict the oldest.

The idea

The map gives O(1) lookup from key to node, and the list keeps the usage order with the most recent at the head. Because each node knows its neighbours, moving it to the front or evicting the tail are both O(1) pointer rewrites.

The trick

  • get must also move the node to the front — reading counts as use.
  • Evict from the tail when the capacity is exceeded, removing the map entry too.
  • Dummy head and tail nodes remove every edge case.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
1
1
2
2
1
3
3
2
0
1
2
3
4
5
6
7
8

Step 1 of 2. Here's the example — cap=2; put(1,1),put(2,2),get(1),put(3,3),get(2) Values: 2, 1, 1, 2, 2, 1, 3, 3, 2.

1/2
Optimal
timeO(1)spaceO(cap)
1hashmap key->node; doubly linked list by recency2get: move node to front3put: insert front; if over capacity remove tail

Input

array
[2, 1, 1, 2, 2, 1, 3, 3, 2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
cap=2; put(1,1),put(2,2),get(1),put(3,3),get(2)
Output:
get(2) = -1

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.