Log inSign up
mediumLeetCodeNot Started

LRU Cache

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

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.

Example 1 · Example 1:

Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation: LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 104
  • 0 <= value <= 105
  • At most 2 * 105 calls will be made to get and put.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for LRU Cache.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • LRU Cache
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Basic prototyping where capacity is very small.
  • BETTER: Rapid industry implementations where standard library LinkedHashMap or Map is approved.
  • OPTIMAL: The universally demanded canonical solution for technical interviews and production high-performance caching.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Array with Linear Search and Timestamps

Intuition

Store all cache elements in an array where each record contains (key, value, timestamp). - get(key): Linear scan through the array for key. If found, increment global timestamp, update record timestamp, and return value. Else return -1. - put(key, value): Linear scan. If key found, update value and timestamp. If absent and capacity full, scan to find record with minimal timestamp, remove it, and append new entry. Scanning requires O(C) time per operation where C is capacity.

When to apply: Basic prototyping where capacity is very small.

Algorithm

  1. Step 1: Maintain an array of { key, value, time } objects and an auto-incrementing timer.
  2. Step 2: On get, iterate through array to locate key. Update time and return value if found, else -1.
  3. Step 3: On put, locate key. If found, update value and time.
  4. Step 4: If key is new and size == capacity, scan to find index with min time and erase it.
  5. Step 5: Push new entry with updated time.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct Item {
5 int key, value, time;
6};
7
8class LRUCacheBrute {
9 int capacity;
10 int timer = 0;
11 std::vector<Item> cache;
12public:
13 LRUCacheBrute(int cap) : capacity(cap) {}
14
15 int get(int key) {
16 for (auto& item : cache) {
17 if (item.key == key) {
18 item.time = ++timer;
19 return item.value;
20 }
21 }
22 return -1;
23 }
24
25 void put(int key, int value) {
26 for (auto& item : cache) {
27 if (item.key == key) {
28 item.value = value;
29 item.time = ++timer;
30 return;
31 }
32 }
33 if ((int)cache.size() >= capacity) {
34 int lruIdx = 0;
35 for (int i = 1; i < (int)cache.size(); ++i) {
36 if (cache[i].time < cache[lruIdx].time) {
37 lruIdx = i;
38 }
39 }
40 cache.erase(cache.begin() + lruIdx);
41 }
42 cache.push_back({key, value, ++timer});
43 }
44};
45
46int main() {
47 LRUCacheBrute lru(2);
48 lru.put(1, 1);
49 lru.put(2, 2);
50 std::cout << lru.get(1) << std::endl;
51 lru.put(3, 3);
52 std::cout << lru.get(2) << std::endl;
53 lru.put(4, 4);
54 std::cout << lru.get(1) << std::endl;
55 std::cout << lru.get(3) << std::endl;
56 std::cout << lru.get(4) << std::endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(C) for get and put where C is cache capacity
  • Space complexity: O(C) auxiliary space

2. Built-in Ordered Map / LinkedHashMap

Intuition

Modern language standard libraries provide data structures that maintain an ordered hash map internally (e.g., Java LinkedHashMap with access-order mode, or JS Map where keys are deleted and re-inserted to move to the back): - get(key): Retrieve value. If present, delete and re-insert or record access so it becomes the most recently used element. - put(key, value): If key exists, update and move to most recently used. If new and capacity full, evict the first key (map.keys().next().value). While practical and clean, this relies on runtime language internals rather than explicit algorithmic pointer manipulation.

When to apply: Rapid industry implementations where standard library LinkedHashMap or Map is approved.

Algorithm

  1. Step 1: Initialize an ordered map.
  2. Step 2: On get(key), if missing return -1. Otherwise reinsert key to update recency and return value.
  3. Step 3: On put(key, value), if key exists, delete it first.
  4. Step 4: If key is new and size == capacity, delete the first (oldest) key in the map.
  5. Step 5: Insert (key, value) into map.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <list>
3#include <unordered_map>
4
5class LRUCacheList {
6 int capacity;
7 std::list<std::pair<int, int>> order; // pair of (key, value)
8 std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
9public:
10 LRUCacheList(int cap) : capacity(cap) {}
11
12 int get(int key) {
13 auto it = map.find(key);
14 if (it == map.end()) return -1;
15 int val = it->second->second;
16 order.erase(it->second);
17 order.push_front({key, val});
18 map[key] = order.begin();
19 return val;
20 }
21
22 void put(int key, int value) {
23 auto it = map.find(key);
24 if (it != map.end()) {
25 order.erase(it->second);
26 } else if ((int)map.size() >= capacity) {
27 int oldKey = order.back().first;
28 map.erase(oldKey);
29 order.pop_back();
30 }
31 order.push_front({key, value});
32 map[key] = order.begin();
33 }
34};
35
36int main() {
37 LRUCacheList lru(2);
38 lru.put(1, 1);
39 lru.put(2, 2);
40 std::cout << lru.get(1) << std::endl;
41 lru.put(3, 3);
42 std::cout << lru.get(2) << std::endl;
43 lru.put(4, 4);
44 std::cout << lru.get(1) << std::endl;
45 std::cout << lru.get(3) << std::endl;
46 std::cout << lru.get(4) << std::endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(1) average time per operation
  • Space complexity: O(capacity) space

3. Hash Map + Custom Doubly Linked List

Intuition

The gold standard design for an LRU cache uses an explicit Doubly Linked List with dummy head and dummy tail nodes paired with an unordered map: 1. Doubly Linked List Structure: - head <-> node_most_recent <-> ... <-> node_least_recent <-> tail - Inserting a node right after head takes 4 pointer updates: O(1). - Deleting any node given its pointer takes 2 pointer updates: O(1). 2. Hash Map Lookup: - map stores key -> Node*. 3. Operations: - get(key): If not in map, return -1. Otherwise, unlink the node from its current position and insert it immediately after head. Return its value. - put(key, value): If key exists, update its value and move to head. If key does not exist and cache is at capacity, delete the node immediately before tail (tail.prev), remove it from the map, and create the new node at the head. Every operation executes in guaranteed, deterministic O(1) time with no standard library overhead.

When to apply: The universally demanded canonical solution for technical interviews and production high-performance caching.

Algorithm

  1. Step 1: Create a Doubly Linked List node class with key, value, prev, and next pointers.
  2. Step 2: Initialize LRUCache with dummy head and tail connected together, and an empty hash map.
  3. Step 3: Implement helper methods addNode(node) (inserts at head) and removeNode(node) (unlinks node).
  4. Step 4: On get(key), if missing return -1. Else removeNode and addNode to make it MRU, then return value.
  5. Step 5: On put(key, value), if key exists, update value and move to MRU. Else if full, evict tail.prev from list and map, then create and insert new node at head.

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
put(1, 1), put(2, 2): Insert keys 1 and 2
Visual state
Values and pointers at this exact step
pointers
S
2
1
0
1
↑ tail
Check / comparison
Both keys inserted at head
Decision / next transition
map has keys {1, 2}
Why this step matters

put(1, 1), put(2, 2): Insert keys 1 and 2. Head -> 2 -> 1 -> Tail. Capacity is 2/2.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3
4struct Node {
5 int key, value;
6 Node *prev, *next;
7 Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
8};
9
10class LRUCache {
11 int capacity;
12 Node *head, *tail;
13 std::unordered_map<int, Node*> map;
14
15 void addNode(Node* node) {
16 node->next = head->next;
17 node->prev = head;
18 head->next->prev = node;
19 head->next = node;
20 }
21
22 void removeNode(Node* node) {
23 node->prev->next = node->next;
24 node->next->prev = node->prev;
25 }
26
27 void moveToHead(Node* node) {
28 removeNode(node);
29 addNode(node);
30 }
31
32 Node* popTail() {
33 Node* res = tail->prev;
34 removeNode(res);
35 return res;
36 }
37
38public:
39 LRUCache(int cap) : capacity(cap) {
40 head = new Node(0, 0);
41 tail = new Node(0, 0);
42 head->next = tail;
43 tail->prev = head;
44 }
45
46 int get(int key) {
47 auto it = map.find(key);
48 if (it == map.end()) return -1;
49 moveToHead(it->second);
50 return it->second->value;
51 }
52
53 void put(int key, int value) {
54 auto it = map.find(key);
55 if (it != map.end()) {
56 it->second->value = value;
57 moveToHead(it->second);
58 return;
59 }
60 if ((int)map.size() >= capacity) {
61 Node* lru = popTail();
62 map.erase(lru->key);
63 delete lru;
64 }
65 Node* newNode = new Node(key, value);
66 map[key] = newNode;
67 addNode(newNode);
68 }
69};
70
71int main() {
72 LRUCache lru(2);
73 lru.put(1, 1);
74 lru.put(2, 2);
75 std::cout << lru.get(1) << std::endl;
76 lru.put(3, 3);
77 std::cout << lru.get(2) << std::endl;
78 lru.put(4, 4);
79 std::cout << lru.get(1) << std::endl;
80 std::cout << lru.get(3) << std::endl;
81 std::cout << lru.get(4) << std::endl;
82 return 0;
83}

Time & Space Complexity

  • Time complexity: O(1) strict time complexity for both get and put
  • Space complexity: O(capacity) auxiliary space for storing nodes and hash map

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array with Linear Search and TimestampsO(C) for get and put where C is cache capacityO(C) auxiliary spaceStore items in an array with an access timestamp. Scan linearly to find keys and evict the oldest timestamp on overflow.O(C) for get and put where C is cache capacity
2.Built-in Ordered Map / LinkedHashMapO(1) average time per operationO(capacity) spaceUse built-in ordered key-value mappings like Java's LinkedHashMap or JavaScript's Map which preserve insertion order.O(1) average time per operation
3.Hash Map + Custom Doubly Linked ListOptimalO(1) strict time complexity for both get and putO(capacity) auxiliary space for storing nodes and hash mapCombine a hash map for O(1) node lookup with a doubly linked list with dummy head and tail for strict O(1) node detachment and insertion.O(1) strict time complexity for both get and put

Common Pitfalls & Crucial Edge Cases

Forgetting to update node order on `get()`

Accessing a key counts as a use, so it MUST be moved to the head of the list.

Memory leak during eviction

Forgetting to remove the evicted tail's key from the Hash Map (map.erase(tail.prev.key)).

Using built-in `std::list` without understanding underlying pointers

Interviewers often ask candidates to implement the Doubly Linked List manually with raw pointers.

Crucial Edge Cases to Validate:

  • capacity = 1 — Constant eviction on every unique put.
  • Updating an existing key — Updates the value and moves the node to the head without increasing size or triggering eviction.
  • Accessing non-existent key via `get` — Returns -1 without modifying list order.
  • Evicting the tail when capacity is reached — Must delete both the node from the Doubly Linked List and its corresponding entry from the Hash Map.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the two primitives immediately: moveToHead(node) and removeNode(node).
  2. Draw the doubly linked list with sentinel head <-> tail nodes on the whiteboard.
  3. Mention production use cases: Redis LRU eviction policies, Linux page cache, and database buffer pools.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What combination of data structures implements LRU Cache in O(1) time?

2.Why is a Doubly Linked List preferred over a Singly Linked List?

3.Why should sentinel dummy head and tail nodes be used in the Doubly Linked List?

Back to DSA Sheet