LRU Cache solution and explanation
9 more videos on this problem
LRU Cache - Twitch Interview Question - Leetcode 146NeetCode · 17:49 · 519K views
LeetCode 146. LRU Cache (Algorithm Explained)Nick White · 18:00 · 131K views
How to Implement an LRU Cache (Leetcode #146 explained)Byte by Byte · 10:32 · 43K views
LRU cache | Leetcode #146Techdose · 6:33 · 28K views
LRU cache | Live Coding with Explanation | Leetcode #146Algorithms Made Easy · 9:02 · 10K views
LRU Cache || Leetcode 146 || Variant Question Big Tech Actually AsksCoding with Minmer · 23:58 · 10K views
LRU CACHE | LEETCODE 146 | PYTHON LINKED LIST SOLUTIONCracking FAANG · 15:30 · 8K views
LEETCODE 146 (JAVASCRIPT) | LRU CACHEAndy Gala · 17:42 · 6K views
[Java] Leetcode 146. LRU Cache [Design #1]Eric Programming · 16:33 · 5K views
LRU Cache LeetCode 146 Solution ExplainedCodingNinja · 17:54 · 5K views
The problem
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 sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
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 <= 30000 <= key <= 1040 <= value <= 105- At most
2 * 105calls will be made togetandput.
Approach overview
Problem Overview: Design a data structure that behaves like a Least Recently Used (LRU) cache. The cache has a fixed capacity and supports two operations: get(key) and put(key, value). When the cache exceeds capacity, it must evict the least recently used item. Both operations must run in O(1) time.
Approach 1: Doubly Linked List with HashMap (O(1) time, O(n) space)
This is the standard interview solution. Combine a hash table with a doubly linked list. The hash map stores key → node so you can locate nodes instantly. The doubly linked list maintains usage order: the most recently used node sits near the head, and the least recently used node sits near the tail. On every get, move the accessed node to the front. On put, either update the existing node or insert a new node at the front. If capacity is exceeded, remove the node at the tail. Each operation performs constant-time pointer updates and hash lookups, giving O(1) time per operation and O(n) space for storing up to capacity nodes.
Approach 2: Ordered Dictionary / Built-in Ordered Map (O(1) time, O(n) space)
Some languages provide a library structure that already maintains insertion order. Python’s OrderedDict or modern dictionary methods, and JavaScript’s Map, allow you to reorder keys efficiently. The idea is simple: when a key is accessed, remove it and reinsert it so it becomes the most recent entry. When inserting a new key that exceeds capacity, remove the first element (the least recently used). Each lookup and update still runs in O(1) average time due to the underlying hash table. Space usage remains O(n) because the structure stores up to capacity key-value pairs.
Recommended for interviews: Interviewers typically expect the Doubly Linked List + HashMap design. It demonstrates strong understanding of system design style problems, pointer manipulation, and constant-time eviction strategies. The library-based solution works in production code but hides the core idea. Showing the manual design proves you understand how LRU eviction actually works under the hood.
Approach 1: Doubly Linked List with HashMap
This approach combines a Doubly Linked List with a HashMap to maintain the LRU functionality. The doubly linked list keeps track of the order of elements. The head of the list represents the most recently used item, whereas the tail represents the least recently used item. Through a HashMap, we achieve O(1) access time complexity for updating and retrieving values. On cache misses that result in a new insertion when the cache is full, we evict the last node of the list.
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
prev = node.prev
next = node.next
prev.next, next.prev = next, prev
def _add(self, node):
n = self.head.next
self.head.next = node
node.prev = self.head
node.next = n
n.prev = node
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self._add(node)
self.cache[key] = node
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]import java.util.*;
class LRUCache {
class Node {
int key, value;
Node prev, next;
Node(int k, int v) {
key = k;
value = v;
}
}
private final int capacity;
private Map<Integer, Node> cache;
private Node head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
private void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
}
private void addToHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
public int get(int key) {
if (cache.containsKey(key)) {
Node node = cache.get(key);
remove(node);
addToHead(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
remove(cache.get(key));
}
if (cache.size() == capacity) {
cache.remove(tail.prev.key);
remove(tail.prev);
}
Node node = new Node(key, value);
addToHead(node);
cache.put(key, node);
}
}The Python solution defines a node class to handle key-value pairs and handles the LRU logic in the LRUCache class. The nodes are stored in a doubly linked list, allowing quick updates and removals. The cache (dictionary) maps keys to their nodes, providing O(1) time complexity for get and put operations.
Time Complexity: O(1) for both get and put operations due to the hashmap and linked list. Space Complexity: O(n), where n is the capacity of the cache for the hashmap and linked list.
Approach 2: Ordered Dictionary (Library Specific)
This approach leverages built-in ordered dictionary data structures available in some languages. These structures inherently maintain the order of insertion, allowing for easy eviction of the least recently used item.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last = False)class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
}
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
this.cache.delete(this.cache.keys().next().value);
}
}
}This Python solution uses the OrderedDict from the collections module. The inherent order tracking of OrderedDict facilitates moving accessed elements to the front or end of the dictionary easily, simplifying the logic for keeping track of least recently used items.
Time Complexity: O(1) for get and put since OrderedDict operations are optimized for simplicity and efficiency. Space Complexity: O(n), with n being the capacity of the cache.
Approach 3: Hash Table + Doubly Linked List
We can implement an LRU (Least Recently Used) cache using a "hash table" and a "doubly linked list".
- Hash Table: Used to store the key and its corresponding node location.
- Doubly Linked List: Used to store node data, sorted by access time.
When accessing a node, if the node exists, we delete it from its original position and reinsert it at the head of the list. This ensures that the node stored at the tail of the list is the least recently used node. When the number of nodes exceeds the maximum cache space, we eliminate the node at the tail of the list.
When inserting a node, if the node exists, we delete it from its original position and reinsert it at the head of the list. If it does not exist, we first check if the cache is full. If it is full, we delete the node at the tail of the list and insert the new node at the head of the list.
The time complexity is O(1), and the space complexity is O(capacity).
class LRUCache {
private:
struct Node {
int key, val;
Node* prev;
Node* next;
Node(int key, int val)
: key(key)
, val(val)
, prev(nullptr)
, next(nullptr) {}
};
int size;
int capacity;
Node* head;
Node* tail;
unordered_map<int, Node*> cache;
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
public:
LRUCache(int capacity)
: size(0)
, capacity(capacity) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.contains(key)) {
return -1;
}
Node* node = cache[key];
removeNode(node);
addToHead(node);
return node->val;
}
void put(int key, int value) {
if (cache.contains(key)) {
Node* node = cache[key];
removeNode(node);
node->val = value;
addToHead(node);
} else {
Node* node = new Node(key, value);
cache[key] = node;
addToHead(node);
if (++size > capacity) {
node = tail->prev;
cache.erase(node->key);
removeNode(node);
--size;
}
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/class Node {
key: number;
val: number;
prev: Node | null;
next: Node | null;
constructor(key: number, val: number) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
class LRUCache {
private size: number;
private capacity: number;
private head: Node;
private tail: Node;
private cache: Map<number, Node>;
constructor(capacity: number) {
this.size = 0;
this.capacity = capacity;
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
this.cache = new Map();
}
get(key: number): number {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key)!;
this.removeNode(node);
this.addToHead(node);
return node.val;
}
put(key: number, value: number): void {
if (this.cache.has(key)) {
const node = this.cache.get(key)!;
this.removeNode(node);
node.val = value;
this.addToHead(node);
} else {
const node = new Node(key, value);
this.cache.set(key, node);
this.addToHead(node);
if (++this.size > this.capacity) {
const nodeToRemove = this.tail.prev!;
this.cache.delete(nodeToRemove.key);
this.removeNode(nodeToRemove);
--this.size;
}
}
}
private removeNode(node: Node): void {
if (!node) return;
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
private addToHead(node: Node): void {
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/public class LRUCache {
private int size;
private int capacity;
private Dictionary<int, Node> cache = new Dictionary<int, Node>();
private Node head = new Node();
private Node tail = new Node();
public LRUCache(int capacity) {
this.capacity = capacity;
head.Next = tail;
tail.Prev = head;
}
public int Get(int key) {
if (!cache.ContainsKey(key)) {
return -1;
}
Node node = cache[key];
RemoveNode(node);
AddToHead(node);
return node.Val;
}
public void Put(int key, int value) {
if (cache.ContainsKey(key)) {
Node node = cache[key];
RemoveNode(node);
node.Val = value;
AddToHead(node);
} else {
Node node = new Node(key, value);
cache[key] = node;
AddToHead(node);
if (++size > capacity) {
node = tail.Prev;
cache.Remove(node.Key);
RemoveNode(node);
--size;
}
}
}
private void RemoveNode(Node node) {
node.Prev.Next = node.Next;
node.Next.Prev = node.Prev;
}
private void AddToHead(Node node) {
node.Next = head.Next;
node.Prev = head;
head.Next = node;
node.Next.Prev = node;
}
// Node class to represent each entry in the cache.
private class Node {
public int Key;
public int Val;
public Node Prev;
public Node Next;
public Node() {}
public Node(int key, int val) {
Key = key;
Val = val;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.Get(key);
* obj.Put(key,value);
*/type Node struct {
key, val int
prev, next *Node
}
type LRUCache struct {
size, capacity int
head, tail *Node
cache map[int]*Node
}
func Constructor(capacity int) LRUCache {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
head: head,
tail: tail,
cache: make(map[int]*Node),
}
}
func (this *LRUCache) Get(key int) int {
if node, exists := this.cache[key]; exists {
this.removeNode(node)
this.addToHead(node)
return node.val
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if node, exists := this.cache[key]; exists {
this.removeNode(node)
node.val = value
this.addToHead(node)
} else {
node := &Node{key: key, val: value}
this.cache[key] = node
this.addToHead(node)
if this.size++; this.size > this.capacity {
node = this.tail.prev
delete(this.cache, node.key)
this.removeNode(node)
this.size--
}
}
}
func (this *LRUCache) removeNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) addToHead(node *Node) {
node.next = this.head.next
node.prev = this.head
this.head.next = node
node.next.prev = node
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
struct Node {
key: i32,
value: i32,
prev: Option<Rc<RefCell<Node>>>,
next: Option<Rc<RefCell<Node>>>,
}
impl Node {
#[inline]
fn new(key: i32, value: i32) -> Self {
Self {
key,
value,
prev: None,
next: None,
}
}
}
struct LRUCache {
capacity: usize,
cache: HashMap<i32, Rc<RefCell<Node>>>,
head: Option<Rc<RefCell<Node>>>,
tail: Option<Rc<RefCell<Node>>>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl LRUCache {
fn new(capacity: i32) -> Self {
Self {
capacity: capacity as usize,
cache: HashMap::new(),
head: None,
tail: None,
}
}
fn get(&mut self, key: i32) -> i32 {
match self.cache.get(&key) {
Some(node) => {
let node = Rc::clone(node);
self.remove(&node);
self.push_front(&node);
let value = node.borrow().value;
value
}
None => -1,
}
}
fn put(&mut self, key: i32, value: i32) {
match self.cache.get(&key) {
Some(node) => {
let node = Rc::clone(node);
node.borrow_mut().value = value;
self.remove(&node);
self.push_front(&node);
}
None => {
let node = Rc::new(RefCell::new(Node::new(key, value)));
self.cache.insert(key, Rc::clone(&node));
self.push_front(&node);
if self.cache.len() > self.capacity {
let back_key = self.pop_back().unwrap().borrow().key;
self.cache.remove(&back_key);
}
}
};
}
fn push_front(&mut self, node: &Rc<RefCell<Node>>) {
match self.head.take() {
Some(head) => {
head.borrow_mut().prev = Some(Rc::clone(node));
node.borrow_mut().prev = None;
node.borrow_mut().next = Some(head);
self.head = Some(Rc::clone(node));
}
None => {
self.head = Some(Rc::clone(node));
self.tail = Some(Rc::clone(node));
}
};
}
fn remove(&mut self, node: &Rc<RefCell<Node>>) {
match (node.borrow().prev.as_ref(), node.borrow().next.as_ref()) {
(None, None) => {
self.head = None;
self.tail = None;
}
(None, Some(next)) => {
self.head = Some(Rc::clone(next));
next.borrow_mut().prev = None;
}
(Some(prev), None) => {
self.tail = Some(Rc::clone(prev));
prev.borrow_mut().next = None;
}
(Some(prev), Some(next)) => {
next.borrow_mut().prev = Some(Rc::clone(prev));
prev.borrow_mut().next = Some(Rc::clone(next));
}
};
}
fn pop_back(&mut self) -> Option<Rc<RefCell<Node>>> {
match self.tail.take() {
Some(tail) => {
self.remove(&tail);
Some(tail)
}
None => None,
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Doubly Linked List with HashMap | Time Complexity: O(1) for both |
| Ordered Dictionary (Library Specific) | Time Complexity: O(1) for |
| Hash Table + Doubly Linked List | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Doubly Linked List + HashMap | O(1) per get/put | O(n) | Standard interview solution when constant-time eviction is required |
| Ordered Dictionary / Map | O(1) average | O(n) | When language libraries provide ordered maps and implementation simplicity matters |
Frequently asked questions
Is LRU Cache easy or hard?
LRU Cache is generally rated Medium on platforms like LeetCode. The logic is straightforward once you understand the combination of HashMap and Doubly Linked List, but implementing pointer updates correctly during insert, move, and eviction can be tricky during interviews.
LRU Cache Python/Java solution
In Python, the optimal solution uses a dictionary plus a custom doubly linked list, or the built-in OrderedDict to manage order. In Java, developers commonly use HashMap with a custom doubly linked list node structure. Both implementations achieve O(1) time for get and put operations.
How to solve LRU Cache in O(n)?
The optimal solution actually achieves O(1) time per operation rather than O(n). Use a hash table to locate nodes instantly and a doubly linked list to maintain usage order. Each get or put only updates pointers or performs a hash lookup, so operations stay constant time regardless of cache size.
What is the best approach for LRU Cache?
The most common approach uses a HashMap combined with a Doubly Linked List. The hash map provides O(1) access to nodes by key, while the doubly linked list maintains the order of recently used items. The head represents the most recently used element and the tail represents the least recently used, enabling O(1) eviction when capacity is exceeded.
Is LRU Cache asked at Google/Amazon/Meta?
LRU Cache is a classic design problem frequently asked in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests knowledge of hash tables, linked lists, and system design concepts such as cache eviction strategies and constant-time operations.
What data structure is used in LRU Cache?
The typical implementation uses two data structures: a HashMap and a Doubly Linked List. The HashMap maps keys to nodes for O(1) access, while the Doubly Linked List tracks usage order so the least recently used element can be removed efficiently.
What is the time complexity of LRU Cache?
A properly designed LRU Cache supports both get(key) and put(key, value) operations in O(1) time. This is achieved by combining constant-time hash table lookups with constant-time node insertions and removals in a doubly linked list. Space complexity is O(n), where n is the cache capacity.