Author at SyntaxFlow
LRU stands for Least Recently Used. An LRU Cache is a fixed-size data structure that stores a limited number of key-value pairs. When the cache is full and a new item needs to be inserted, it evicts (removes) the item that was used least recently — i.e., the item that hasn't been accessed for the longest time.
In simple words:
LRU is not just a textbook exercise — it powers real systems you use every day:
📌 Note: This problem is popular precisely because it tests multiple skills at once — hash maps, linked lists, pointer manipulation, and time-complexity reasoning — all in one question.
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 it exists, otherwise return -1.void put(int key, int value) — Update the value of the key if it 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.
The capacity is the maximum number of key-value pairs the cache can hold at any time. Once this limit is reached, inserting a new key requires evicting an old one — specifically, the one that was least recently accessed.
get(key)key exists in the cache → return its value and mark it as recently used.key does not exist → return -1 (cache miss).put(key, value)key already exists → update its value and mark it as recently used.key doesn't exist:🧠 Key Rule: "Recently used" means recently accessed viaget()OR recently inserted/updated viaput(). Any touch to a key refreshes its recency.
The eviction always removes the item that has gone the longest without being touched.
Example 1
Input:
LRUCache lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
lru.get(1); // returns 1
lru.put(3, 3); // evicts key 2
lru.get(2); // returns -1 (not found)
lru.put(4, 4); // evicts key 1
lru.get(1); // returns -1 (not found)
lru.get(3); // returns 3
lru.get(4); // returns 4Explanation with cache state after every operation (Most Recently Used → Least Recently Used, left to right):
Example 2 (Capacity = 1)
LRUCache lru = new LRUCache(1);
lru.put(5, 100); // cache: {5=100}
lru.get(5); // returns 100
lru.put(6, 200); // evicts 5, cache: {6=200}
lru.get(5); // returns -1
lru.get(6); // returns 200With capacity 1, every new key evicts the previous one, since only one item can exist at a time.
Typical constraints (as seen on LeetCode #146):
1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^52 * 10^5 calls will be made to get and put.get and put must run in O(1) average time complexity.⚠️ Important: The O(1) requirement is the whole point of this problem. Any solution that uses O(n) search or O(n) deletion will technically produce correct output but will fail on time limits for large inputs (up to 2×10⁵ operations).
Before writing any code, let's build the right mental model.
If we store (key, value) pairs in a plain array or vector:
This clearly violates the O(1) requirement.
Without an index (like a hash map), locating a key means checking every element one by one. As the cache grows toward its capacity limit (up to 3000, and total operations up to 2×10⁵), linear search becomes a bottleneck.
Even if we knew where an element was, removing it from the middle of an array requires shifting all elements after it to fill the gap — again O(n).
This is why arrays (and even singly linked lists, as we'll see) struggle here: deletion from an arbitrary position is expensive unless we use a structure that supports O(1) removal given a pointer to the node.
Since the problem explicitly demands O(1) average time for both get and put, we need:
Neither structure alone is sufficient — we need both, working together.
A HashMap<key, Node*> lets us jump directly to the node holding a given key in O(1) average time, instead of searching for it. This solves the "search" problem instantly.
But a HashMap alone can't tell us which key was least recently used — hash maps have no inherent ordering. That's where the linked list comes in.
We need a structure that maintains usage order: most recently used at one end, least recently used at the other. Whenever a key is accessed, we move its node to the "most recently used" end.
A Doubly Linked List (DLL) allows:
prev and next pointers).In a Singly Linked List, each node only knows its next node — not its previous one.
To remove a node from a singly linked list, you need the previous node's reference to skip over it (prev->next = node->next). Since we don't have a prev pointer, we'd have to traverse from the head to find it → O(n).
This defeats the purpose. Only a Doubly Linked List gives us O(1) deletion given just a pointer to the node itself, which is exactly what our HashMap provides us.
Use a simple vector (or array) of (key, value) pairs. To track recency, whenever a key is accessed, remove it from its current position and push it to the front (or back) of the vector. Eviction removes the last element.
vector<pair<int,int>> cache and an integer capacity.get(key):key.-1.put(key, value):key.capacity (and we're inserting a brand-new key), remove the last element (least recently used).(key, value) at the front.Dry Run
#include <bits/stdc++.h>
using namespace std;
class LRUCacheBrute {
private:
int capacity;
vector<pair<int,int>> cache; // front = most recently used
public:
LRUCacheBrute(int cap) : capacity(cap) {}
int get(int key) {
for (int i = 0; i < (int)cache.size(); i++) {
if (cache[i].first == key) {
pair<int,int> entry = cache[i];
cache.erase(cache.begin() + i); // O(n) removal
cache.insert(cache.begin(), entry); // O(n) insertion at front
return entry.second;
}
}
return -1;
}
void put(int key, int value) {
for (int i = 0; i < (int)cache.size(); i++) {
if (cache[i].first == key) {
cache.erase(cache.begin() + i); // remove old entry
break;
}
}
if ((int)cache.size() == capacity) {
cache.pop_back(); // evict least recently used
}
cache.insert(cache.begin(), {key, value});
}
};get() → O(n) (linear search + shifting)put() → O(n) (linear search + shifting + possible eviction)Improve lookup speed using a HashMap for O(1) key lookup, but still use a singly linked list (or a list with only "next" pointers) to track order. This partially optimizes search but deletion is still slow because we can't jump backward.
unordered_map<int, value> for value lookup.list<int> used naively) to track usage order, where we still need to search for a node's position to remove it.unordered_map<int,int> valueMap for key -> value.std::list<int>) storing keys in order of use (front = most recent).get(key):valueMap, return -1.valueMap[key].put(key, value):prev node).capacity = 2
Note: We are not providing a full implementation of the Better Approach because it is not commonly implemented in interviews. Its purpose is to illustrate why using a HashMap + Linked List alone is still insufficient. Since the HashMap stores only the values and not the node locations, we must traverse the linked list to locate a key before moving it to the front, resulting in O(n) time forget()and updating an existing key input(). Understanding this limitation is more important than memorizing the code, as interviewers typically expect the optimal O(1) solution using a HashMap that stores node pointers along with a Doubly Linked List.
int get(int key) {
if (valueMap.find(key) == valueMap.end())
return -1; // cache miss — this check is O(1)
// Search the usage order to find where this key currently sits
removeKeyFromOrder(key); // O(n) — must scan the whole list
order.insert(order.begin(), key); // move it to the front
return valueMap[key];
}get() → O(n) in the worst case (due to findInList scan), though hashmap lookup itself is O(1).put() → O(n) in the worst case for the same reason.Pros:
valueMap.find) is O(1) — a genuine improvement over brute force.Cons:
get/put requirement.💡 The missing piece: we need the hashmap to store not just the value, but a direct pointer to the node in the list — so we can splice it out in O(1) without any search. That's exactly what the optimal approach does.
The fix to the "Better Approach" is simple but powerful: instead of storing key → value in the hashmap, store key → node pointer. That way, given any key, we can jump directly to its node in the linked list in O(1) — no traversal needed — and since it's a doubly linked list, we can unlink and relink it in O(1) too.
Together, these two structures give us true O(1) average time for every operation.
Each node in the doubly linked list stores:
class Node {
public:
int key; // needed so we can remove it from the hashmap during eviction
int value;
Node* prev;
Node* next;
};📌 Why storekeyinside the node? When we evict the least recently used node, we only have aNode*pointer (from the tail side) — we don't automatically know its key. Storing the key inside the node lets us docache.erase(node->key)in O(1) without any extra lookup.
We maintain two dummy (sentinel) nodes:
head → a placeholder marking the most recently used side.tail → a placeholder marking the least recently used side.Real nodes always live between head and tail.
head is always the most recently used.tail is always the least recently used (eviction target).Without dummy nodes, we'd need to constantly check "is this the first node?" or "is this the last node?" with if (head == nullptr) style edge-case handling scattered everywhere.
With dummy head and tail nodes:
insertAfterHead(node) — no special case for an empty list.tail->prev — no special case for checking if the list is empty (as long as capacity >= 1 and we only evict when full).if node->prev == nullptr — because a real node's prev is never nullptr; it's at worst the head dummy.✅ Callout: Dummy nodes trade a tiny bit of extra memory (2 nodes) for eliminating an entire category of null-pointer edge cases. This is a widely used technique in linked-list based interview problems.
removeNode(Node* node)
Unlinks a node from wherever it currently sits in the list by rewiring its neighbors to point to each other.
void removeNode(Node* node) {
Node* prevNode = node->prev;
Node* nextNode = node->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
}This works regardless of where the node is (front, middle, or just before tail) — that's the power of a doubly linked list. Runs in O(1).
insertAfterHead(Node* node)
Inserts a node right after the dummy head, making it the new "most recently used" node.
void insertAfterHead(Node* node) {
Node* nextNode = head->next;
head->next = node;
node->prev = head;
node->next = nextNode;
nextNode->prev = node;
}Runs in O(1) — always a fixed 4-pointer rewire.
moveToFront(Node* node)
Simply combines the two helpers above: remove the node from its current spot, then reinsert it right after head.
void moveToFront(Node* node) {
removeNode(node);
insertAfterHead(node);
}This is called whenever a key is accessed via get() or updated via put(), since both actions make that key the most recently used.
get(key) — Step by Stepkey exists in the hashmap.-1.Node* from the hashmap.moveToFront(node) to mark it as most recently used.node->value.put(key, value) — Step by StepNode* from the hashmap.node->value = value.moveToFront(node).cache.size() == capacity (cache is full):tail->prev.removeNode().Node(key, value).cache[key] = newNode.insertAfterHead(newNode) to place it as most recently used.📌 Note: The order of "evict first, then insert" vs "insert first, then evict" doesn't matter functionally as long as you correctly check capacity before adding a brand-new key — never evict when simply updating an existing key.
Let's trace through the exact example requested, with 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)
Step-by-step reasoning for the tricky evictions:
= capacity). The LRU node (tail->prev) is key 2 (since key 1 was refreshed in step 3, making key 2 the least recently used). So key 2 is evicted.#include <unordered_map>
using namespace std;
// Doubly linked list node storing a key-value pair
class Node {
public:
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int capacity;
unordered_map<int, Node*> cache; // key -> node pointer, gives O(1) lookup
Node* head; // dummy head: node right after it = most recently used
Node* tail; // dummy tail: node right before it = least recently used
// Detach a node from its current position in the list. O(1).
void removeNode(Node* node) {
Node* prevNode = node->prev;
Node* nextNode = node->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
}
// Insert a node right after the dummy head (marks it as most recently used). O(1).
void insertAfterHead(Node* node) {
Node* nextNode = head->next;
head->next = node;
node->prev = head;
node->next = nextNode;
nextNode->prev = node;
}
// Move an existing node to the front of the list. O(1).
// Called whenever a key is accessed (get) or updated (put).
void moveToFront(Node* node) {
removeNode(node);
insertAfterHead(node);
}
public:
LRUCache(int cap) {
capacity = cap;
head = new Node(-1, -1); // dummy, value unused
tail = new Node(-1, -1); // dummy, value unused
head->next = tail;
tail->prev = head;
}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) {
return -1; // cache miss
}
Node* node = it->second;
moveToFront(node); // cache hit -> refresh recency
return node->value;
}
void put(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) {
// Key already exists: update value and refresh recency
Node* node = it->second;
node->value = value;
moveToFront(node);
return;
}
// New key: check capacity before inserting
if ((int)cache.size() == capacity) {
// Evict the least recently used node (just before tail)
Node* lru = tail->prev;
removeNode(lru);
cache.erase(lru->key);
delete lru; // free memory to avoid leaks
}
// Insert the new node as most recently used
Node* newNode = new Node(key, value);
cache[key] = newNode;
insertAfterHead(newNode);
}
// Destructor: free all allocated nodes to prevent memory leaks
~LRUCache() {
Node* curr = head;
while (curr != nullptr) {
Node* next = curr->next;
delete curr;
curr = next;
}
}
};We need to prove two things:
Claim 1: The node immediately after head is always the most recently used key, and the node immediately before tail is always the least recently used key.
Proof by invariant: We maintain the invariant that every time a key is touched (via get returning a hit, or put inserting/updating), we immediately call either insertAfterHead() (for new nodes) or moveToFront() (for existing nodes) — both of which place that node directly after head. Since this happens immediately after every touch, and no other operation reorders the list, the node after head is, by induction, always the most recently touched key at any point in time. Since the list is finite and ordered, the node before tail must be the one that has gone the longest without being touched — i.e., the least recently used.
Claim 2: Eviction always removes the correct (least recently used) key.
Proof: Eviction only happens when inserting a brand-new key while cache.size() == capacity. At that moment, by Claim 1, tail->prev is guaranteed to be the least recently used node among all currently cached keys. Removing it and erasing it from the hashmap keeps the hashmap and linked list perfectly synchronized — every key in the hashmap has exactly one corresponding node in the list, and vice versa.
Claim 3: get() and put() always reflect the true current value.
Proof: The hashmap always stores the up-to-date Node* for a key (nodes are updated in place via node->value = value, never replaced), so get() always reads the latest value. Since keys are never duplicated (we check cache.find(key) before creating a new node), each key maps to exactly one node at all times.
Together, these three claims guarantee the algorithm always returns the correct value for get() and always evicts the correct key during put().
cache.find(key)) → O(1) average, since hashing gives direct bucket access.removeNode() → O(1), because we directly access node->prev and node->next — no traversal needed.insertAfterHead() → O(1), because head is a fixed reference point — always a constant number of pointer updates.moveToFront() → O(1), since it's just removeNode() + insertAfterHead(), both O(1).tail->prev gives direct access to the LRU node without any search.🚀 The key insight: O(1) is achievable only because the hashmap gives us the node pointer directly — eliminating the need to search for a node's position before we can remove or reorder it.
Here are common follow-up questions interviewers ask after you present the optimal solution:
mutex to lock around get/put, and mention trade-offs (a global lock hurts concurrency; finer-grained locking is complex due to shared list pointers).capacity >= 1, but you should handle it gracefully (e.g., every put immediately evicts, or you simply never insert).std::list from STL instead of writing your own doubly linked list?" Yes — std::list<pair<int,int>> plus a hashmap of key -> list iterator achieves the same O(1) behavior, since std::list supports O(1) splicing given an iterator. Be ready to discuss why storing an iterator in the map (not just a value) is essential here.prev/next pointers plus a hashmap entry, so it's roughly O(capacity) with a higher constant factor than a plain array — but this is the necessary trade-off for O(1) time.💡 Tip: Always mention why simpler approaches fail (arrays, singly linked lists) before jumping to the optimal solution — interviewers want to see your reasoning process, not just memorized code.
Q1. What is the time complexity of LRU Cache operations? Both get() and put() run in O(1) average time complexity using the HashMap + Doubly Linked List approach.
Q2. Why can't we use only a HashMap for LRU Cache? A HashMap gives O(1) lookup but has no concept of ordering, so it cannot tell us which key was least recently used without additional bookkeeping.
Q3. Why can't we use only a Doubly Linked List without a HashMap? Without a hashmap, finding whether a key exists (and where its node is) would require traversing the list — O(n) — defeating the purpose.
Q4. Why is a Doubly Linked List used instead of a Singly Linked List? Because deletion requires access to a node's previous node too. A singly linked list only knows the next node, forcing an O(n) traversal to find the previous node before deletion.
Q5. What is the purpose of dummy head and tail nodes? They eliminate special-case handling for empty lists or single-node lists, simplifying insertAfterHead() and eviction logic significantly.
Q6. Can I implement LRU Cache using Java's LinkedHashMap? Yes — Java's LinkedHashMap has a built-in "access order" mode and can override removeEldestEntry() to implement LRU in just a few lines, since it internally maintains a doubly linked list already.
Q7. What happens if put() is called with a key that already exists? The value is updated, and the key is marked as most recently used — no eviction occurs since no new key is being added.
Q8. Is LRU Cache related to Operating Systems concepts? Yes — it's directly analogous to the page replacement algorithm used in virtual memory management, where the OS evicts the least recently used memory page when RAM is full.
Q9. What is the space complexity of the optimal LRU Cache solution? O(capacity), since we store exactly one hashmap entry and one linked list node per cached key (plus 2 constant-size dummy nodes).
Q10. How is LRU different from LFU (Least Frequently Used)? LRU evicts based on recency of access (when it was last used), while LFU evicts based on frequency of access (how many times it was used) — different eviction philosophies for different workloads.
Q11. Does the order of checking capacity vs. inserting matter in put()? No, as long as you only evict for brand-new keys and check capacity before the cache would exceed its limit — both "evict-then-insert" and equivalent logic produce identical results.
Q12. Can this problem be solved without a linked list, using an ordered map? In some languages, an ordered structure with efficient reordering (like Python's OrderedDict) can substitute for the manual doubly linked list, since it provides similar O(1) move-to-end/front semantics internally.
get() or put() — must move that node to the "most recently used" position.tail, guaranteed by the maintained invariant.🎯 Final tip: When solving this in an interview, always narrate your reasoning — explain why brute force fails, why HashMap alone fails, and how combining it with a Doubly Linked List solves every bottleneck. This is what separates a "correct" answer from a great answer.
video reference:
code link: