LRU Cache
Implement a least recently used cache. get returns a value or -1. put inserts or updates a key. When full, evict the least recently accessed key. Both operations refresh recency and must take average constant time.
Work through the cases
3 examplesInput notation
Positive capacity on line 1; then commands put key value or get key.Expected result
One integer per get command.Case 1
Input
2 put 1 10 put 2 20 get 1 put 3 30 get 2
Expected output
10 -1
Case 2
Input
1 put 4 7 put 4 9 get 4
Expected output
9
Case 3
Input
1 get 9 put 1 2 put 3 4 get 1 get 3
Expected output
-1 -1 4
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
get and put must be O(1), evicting the least recently used key. A hash map finds keys in O(1) but does not keep recency; moving nodes in an array or singly linked list is O(n). Up to 2 × 10^5 calls. Map keys to nodes, and keep a doubly linked list with most-recent at the head. On access, detach the node and insert it at the head; when over capacity, drop the tail's predecessor. Lookup and pointer updates are O(1).
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 Node {
int key, val;
Node prev, next;
Node() {
}
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
class LRUCache {
private int size;
private int capacity;
private Node head = new Node();
private Node tail = new Node();
private Map<Integer, Node> cache = new HashMap<>();
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.get(key);
removeNode(node);
addToHead(node);
return node.val;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
Node node = cache.get(key);
removeNode(node);
node.val = value;
addToHead(node);
} else {
Node node = new Node(key, value);
cache.put(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;
}
}
/**
* 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);
*/Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.