LRU Cache
Problem
Design a data structure that follows the Least Recently Used (LRU) cache rule. Implement LRUCache(capacity), get(key) (the value, or -1 if missing) and put(key, value) (insert or update).
When a put would exceed the capacity, first evict the key that was used least recently. Both get and put count as a use, and both must run in O(1) average time.
Example 1
- 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) evicts key 2; put(4) evicts key 1.
Constraints
- 1 ≤ capacity ≤ 3000
- At most 2 × 10⁵ calls to get and put.
Explanation
You need two things in O(1): find a key (hash map), and keep keys ordered by recent use so you can move one to the front and drop the oldest (doubly linked list).
The map points from each key to its list node. On every use, unlink the node and put it right after the head. The node just before the tail is the least recently used.
Approach 1 · Naive
Map plus an ordered list of keys
- Time O(n) per operation
- Space O(capacity)
Store values in a map and keep the keys in a list ordered by use. Moving a key means removing it from the list, which is O(n).
get: if present, move the key to the end of the list and return the value.put: update or insert; move the key to the end; if over capacity, remove the first key from the list and the map.
import java.util.*;
class LRUCache {
private final int capacity;
private final Map<Integer, Integer> values = new HashMap<>();
private final List<Integer> order = new ArrayList<>();
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!values.containsKey(key)) {
return -1;
}
order.remove(Integer.valueOf(key));
order.add(key);
return values.get(key);
}
public void put(int key, int value) {
if (values.containsKey(key)) {
order.remove(Integer.valueOf(key));
} else if (values.size() == capacity) {
values.remove(order.remove(0));
}
values.put(key, value);
order.add(key);
}
}class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.values = {}
self.order = []
def get(self, key: int) -> int:
if key not in self.values:
return -1
self.order.remove(key)
self.order.append(key)
return self.values[key]
def put(self, key: int, value: int) -> None:
if key in self.values:
self.order.remove(key)
elif len(self.values) == self.capacity:
del self.values[self.order.pop(0)]
self.values[key] = value
self.order.append(key)Approach 2 · Optimal
Hash map + doubly linked list
- Time O(1) per operation
- Space O(capacity)
Map keys to nodes of a doubly linked list ordered from most to least recently used. Sentinel head and tail nodes remove edge cases.
get: look up the node; if found, move it to the front and return its value.put: if the key exists, update the value and move it to the front.- Otherwise create a node at the front; if the size exceeds capacity, remove
tail.prevfrom the list and the map.
import java.util.*;
class LRUCache {
private static class Entry {
int key;
int value;
Entry prev;
Entry next;
Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Entry> map = new HashMap<>();
private final Entry head = new Entry(0, 0);
private final Entry tail = new Entry(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Entry entry = map.get(key);
if (entry == null) {
return -1;
}
unlink(entry);
addFront(entry);
return entry.value;
}
public void put(int key, int value) {
Entry entry = map.get(key);
if (entry != null) {
entry.value = value;
unlink(entry);
addFront(entry);
return;
}
entry = new Entry(key, value);
map.put(key, entry);
addFront(entry);
if (map.size() > capacity) {
Entry oldest = tail.prev;
unlink(oldest);
map.remove(oldest.key);
}
}
private void unlink(Entry entry) {
entry.prev.next = entry.next;
entry.next.prev = entry.prev;
}
private void addFront(Entry entry) {
entry.next = head.next;
entry.prev = head;
head.next.prev = entry;
head.next = entry;
}
}class Entry:
def __init__(self, key=0, value=0):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.map = {}
self.head, self.tail = Entry(), Entry()
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, entry):
entry.prev.next, entry.next.prev = entry.next, entry.prev
def _add_front(self, entry):
entry.prev, entry.next = self.head, self.head.next
self.head.next.prev = entry
self.head.next = entry
def get(self, key: int) -> int:
entry = self.map.get(key)
if not entry:
return -1
self._unlink(entry)
self._add_front(entry)
return entry.value
def put(self, key: int, value: int) -> None:
entry = self.map.get(key)
if entry:
entry.value = value
self._unlink(entry)
self._add_front(entry)
return
entry = Entry(key, value)
self.map[key] = entry
self._add_front(entry)
if len(self.map) > self.capacity:
oldest = self.tail.prev
self._unlink(oldest)
del self.map[oldest.key]Complexity compared
| Approach | Time | Space |
|---|---|---|
| Naive Map plus an ordered list of keys | O(n) per operation | O(capacity) |
| Optimal Hash map + doubly linked list | O(1) per operation | O(capacity) |
Key takeaways
- Store the key inside each list node, so you can delete it from the map when it is evicted.
- Java's
LinkedHashMap(access order) and Python'sOrderedDictdo this for you; interviewers usually want you to build it.
Your notes
Saved in this browser as you type.
Solved it on your own?
Mark it done to track your progress, or star it to come back before an interview.