43.LRU Cache

MediumLinked List · 9/11

Problem

Design a data structure for a Least Recently Used (LRU) cache with a fixed capacity:

LRUCache(int capacity) — initialise the cache with a positive capacity.
int get(int key) — return the value of key if present, otherwise -1. A successful get counts as a use.
void put(int key, int value) — insert or update key. If the insert pushes the size above capacity, evict the least recently used key.

Both get and put must run in O(1) average time.

Examples

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:
put(1,1), put(2,2)       cache (LRU -> MRU): 1, 2
get(1) = 1               cache: 2, 1
put(3,3) evicts key 2    cache: 1, 3
get(2) = -1
put(4,4) evicts key 1    cache: 3, 4
get(1) = -1, get(3) = 3, get(4) = 4

Input:
["LRUCache", "put", "put", "put", "get"]
[[1], [5, 50], [5, 55], [6, 60], [5]]
Output:
[null, null, null, null, -1]
Explanation: Updating key 5 does not grow the cache; inserting 6 evicts 5.

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.

💡 Key Insight

We need two things in O(1): find a key (a HashMap) and reorder / evict by recency (a list where we can move any node to the front and drop the back). A doubly linked list can unlink any node in O(1) if we already hold a reference to it — and the hash map gives us exactly that reference. Map key → list node; keep the most recent node next to the head sentinel and evict from the tail sentinel.

Brute Force (List Scan)

TimeO(capacity) per operationSpaceO(capacity)

Intuition

Keep [key, value] pairs in an ArrayList ordered from least to most recently used. Every operation scans for the key; "using" an entry means moving it to the end; evicting means removing index 0.

Algorithm

get(key): scan for key; if found, remove it, append it to the end, and return its value; else -1.
put(key, value): if present, remove it. If the list is at capacity, remove index 0. Append [key, value].

Visualization

capacity 2
put(1,1): [(1,1)]
put(2,2): [(1,1), (2,2)]
get(1):   [(2,2), (1,1)]          -> 1
put(3,3): full, drop index 0 -> [(1,1), (3,3)]

Code

java

import java.util.ArrayList;
import java.util.List;

class LRUCache {
    private final int capacity;
    private final List<int[]> entries = new ArrayList<>(); // index 0 = least recent

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        for (int i = 0; i < entries.size(); i++) {
            if (entries.get(i)[0] == key) {
                int[] entry = entries.remove(i);
                entries.add(entry); // mark as most recently used
                return entry[1];
            }
        }
        return -1;
    }

    public void put(int key, int value) {
        for (int i = 0; i < entries.size(); i++) {
            if (entries.get(i)[0] == key) {
                entries.remove(i);
                break;
            }
        }
        if (entries.size() == capacity) {
            entries.remove(0); // evict least recently used
        }
        entries.add(new int[] {key, value});
    }
}

Complexity

Time: O(capacity) per operation — linear scan plus ArrayList.remove shifting.
Space: O(capacity) — one entry per cached key.

LinkedHashMap (Library)

TimeO(1) average per operation.SpaceO(capacity).

Intuition

Java's LinkedHashMap already combines a hash table with a doubly linked list. Constructed with accessOrder = true, every get/put moves the entry to the end, and overriding removeEldestEntry evicts the oldest entry automatically. Great in practice — but interviewers usually want you to build it yourself.

Algorithm

Create new LinkedHashMap<>(capacity, 0.75f, true) and override removeEldestEntry to return size() > capacity.
get → getOrDefault(key, -1); put → put(key, value).

Visualization

accessOrder = true keeps iteration order LRU -> MRU
put 1, put 2      -> {1, 2}
get 1             -> {2, 1}
put 3, size 3 > 2 -> eldest (2) removed -> {1, 3}

Code

java

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache {
    private final Map<Integer, Integer> cache;

    public LRUCache(int capacity) {
        // accessOrder = true: iteration order is least -> most recently accessed
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }
}

Complexity

Time: O(1) average per operation.
Space: O(capacity).

HashMap + Doubly Linked ListOptimal

TimeO(1) average for get and putSpaceO(capacity)

Intuition

Build the structure by hand. Two sentinel nodes, head and tail, bracket the list so insertions and removals never deal with null edges. The node right after head is the most recently used, the node right before tail is the least recently used. The map holds key → node, so any node can be unlinked in O(1).

Algorithm

Helpers: remove(node) unlinks a node; addToFront(node) inserts it right after head.
get(key): if absent return -1. Otherwise remove(node), addToFront(node), return node.value.
put(key, value):
- If present: update value, move to front.
- Else: create a node, put it in the map, add to front. If map.size() > capacity, take lru = tail.prev, remove(lru) and map.remove(lru.key).

Visualization

flowchart LR
    H["head sentinel"] <--> A["key 3<br/>most recent"]
    A <--> B["key 1<br/>least recent"]
    B <--> T["tail sentinel"]
    M["HashMap<br/>1 -> node, 3 -> node"] -.-> A
    M -.-> B

This is the state of Example 1 after put(3,3). On put(4,4) with capacity 2: insert 4 after head, the map grows to 3, so evict tail.prev (key 1) from both the list and the map.

Code

java

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0); // sentinel: after it = most recent
    private final Node tail = new Node(0, 0); // sentinel: before it = least recent

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        remove(node);
        addToFront(node); // mark as most recently used
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            addToFront(node);
            return;
        }
        node = new Node(key, value);
        map.put(key, node);
        addToFront(node);
        if (map.size() > capacity) {
            Node lru = tail.prev; // least recently used
            remove(lru);
            map.remove(lru.key);  // why the node stores its key
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

Complexity

Time: O(1) average for get and put — one hash lookup plus constant pointer updates.
Space: O(capacity) — one map entry and one list node per key.

Complexity Comparison

Approach	Time (per op)	Space
List Scan	O(capacity)	O(capacity)
LinkedHashMap	O(1)	O(capacity)
HashMap + Doubly Linked List	O(1)	O(capacity)

Common Pitfalls

Forgetting that get also updates recency — only moving nodes on put gives wrong evictions.
Not storing the key inside the node — when evicting tail.prev you need its key to remove it from the map.
Evicting before checking whether the key already exists: updating an existing key must never evict anything.
Using a singly linked list — removing an arbitrary node then needs its predecessor, which costs O(n).
Skipping sentinels and then mishandling null when the list has zero or one node.