Approach

LRU Cache

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.

Examples

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 <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put.

Approach

Key Insight

Use HashMap + Doubly Linked List!

HashMap: O(1) lookup by key
Doubly Linked List: O(1) removal and insertion
- Most recently used → Head
- Least recently used → Tail

Data Structures

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):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        self.head = Node(0, 0)  # Dummy head
        self.tail = Node(0, 0)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

Operations

Get(key):

If key not in cache → return -1
Move node to head (most recently used)
Return node.value

Put(key, value):

If key exists → update value, move to head
Else:
- Create new node
- Add to head
- If capacity exceeded → remove tail (LRU)

Complexity Analysis

Time Complexity:

get: O(1) - hash map lookup + list operations
put: O(1) - hash map insert + list operations

Space Complexity:

Overall: O(capacity) - store at most capacity items

Pattern Recognition

This problem demonstrates:

LRU Cache design pattern
HashMap + Doubly Linked List combination
O(1) operations requirement
Dummy nodes technique
Foundation for cache implementations

Solution

java

1import java.util.*;
2
3class LRUCache {
4    /**
5     * LRU Cache using HashMap + Doubly Linked List.
6     *
7     * Time: O(1) for get and put
8     * Space: O(capacity)
9     */
10
11    class Node {
12        int key;
13        int value;
14        Node prev;
15        Node next;
16
17        Node(int key, int value) {
18            this.key = key;
19            this.value = value;
20        }
21    }
22
23    private Map<Integer, Node> cache;
24    private int capacity;
25    private Node head;  // Dummy head
26    private Node tail;  // Dummy tail
27
28    public LRUCache(int capacity) {
29        this.capacity = capacity;
30        this.cache = new HashMap<>();
31
32        // Initialize dummy nodes
33        this.head = new Node(0, 0);
34        this.tail = new Node(0, 0);
35        head.next = tail;
36        tail.prev = head;
37    }
38
39    private void remove(Node node) {
40        // Remove node from linked list
41        Node prevNode = node.prev;
42        Node nextNode = node.next;
43        prevNode.next = nextNode;
44        nextNode.prev = prevNode;
45    }
46
47    private void addToHead(Node node) {
48        // Add node right after head (most recently used)
49        node.prev = head;
50        node.next = head.next;
51        head.next.prev = node;
52        head.next = node;
53    }
54
55    private void moveToHead(Node node) {
56        // Move existing node to head
57        remove(node);
58        addToHead(node);
59    }
60
61    private Node removeTail() {
62        // Remove and return least recently used node
63        Node lru = tail.prev;
64        remove(lru);
65        return lru;
66    }
67
68    public int get(int key) {
69        if (!cache.containsKey(key)) {
70            return -1;
71        }
72
73        // Move to head (mark as recently used)
74        Node node = cache.get(key);
75        moveToHead(node);
76        return node.value;
77    }
78
79    public void put(int key, int value) {
80        if (cache.containsKey(key)) {
81            // Update existing node
82            Node node = cache.get(key);
83            node.value = value;
84            moveToHead(node);
85        } else {
86            // Create new node
87            Node newNode = new Node(key, value);
88            cache.put(key, newNode);
89            addToHead(newNode);
90
91            // Check capacity
92            if (cache.size() > capacity) {
93                // Remove LRU
94                Node lru = removeTail();
95                cache.remove(lru.key);
96            }
97        }
98    }
99}
100
101// Alternative implementation using LinkedHashMap
102class LRUCacheLinkedHashMap extends LinkedHashMap<Integer, Integer> {
103    /**
104     * LRU Cache using LinkedHashMap.
105     *
106     * Time: O(1) for get and put
107     * Space: O(capacity)
108     */
109
110    private int capacity;
111
112    public LRUCacheLinkedHashMap(int capacity) {
113        super(capacity, 0.75f, true);  // accessOrder = true
114        this.capacity = capacity;
115    }
116
117    public int get(int key) {
118        return super.getOrDefault(key, -1);
119    }
120
121    public void put(int key, int value) {
122        super.put(key, value);
123    }
124
125    @Override
126    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
127        return size() > capacity;
128    }
129}
130
131/**
132 * Your LRUCache object will be instantiated and called as such:
133 * LRUCache obj = new LRUCache(capacity);
134 * int param_1 = obj.get(key);
135 * obj.put(key,value);
136 */
137