LRU Cache

MediumLinked ListNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

Design a class LRUCache that holds at most capacity key-value pairs. LRUCache(capacity) creates an empty cache. get(key) returns the value stored for key, or -1 if the key is absent. put(key, value) inserts the pair, or overwrites the value if the key already exists. If inserting a new key would push the size past capacity, evict the least recently used key to make room. A successful get and any put both count as using that key. get and put must each run in O(1) average time.

Examples

LRUCache(2); put(1, 1); put(2, 2); get(1); put(3, 3); get(2); put(4, 4); get(1); get(3); get(4) returns 1, -1, -1, 3, 4

get(1) returns 1 and makes key 1 the most recent, so put(3, 3) evicts key 2 and get(2) returns -1. put(4, 4) then evicts key 1, now the least recently used, so get(1) returns -1 while keys 3 and 4 are still cached.

LRUCache(2); put(1, 1); put(2, 2); put(1, 10); put(3, 3); get(1); get(2) returns 10, -1

put(1, 10) overwrites key 1 without evicting anything, and it counts as a use. That leaves key 2 as the least recently used, so put(3, 3) evicts it.

LRUCache(1); put(1, 1); put(2, 2); get(1); get(2) returns -1, 2

With room for one pair, inserting key 2 evicts key 1 straight away.

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.

Hints

Hint 1

You need two things in constant time: find a key's value, and know which key was touched longest ago. No single built-in structure does both, so think about pairing two.

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Pair a hash map from key to node with a doubly linked list kept in recency order: most recent next to a sentinel head, least recent next to a sentinel tail. get looks the node up, unlinks it and reinserts it at the front. put updates and moves an existing node, or, when the cache is full, first removes the node before tail and its key from the map, then adds the new node at the front. Each step is a lookup or a few pointer changes: O(1) per operation, O(capacity) space.

Time

O(1) per get and put

Space

O(capacity)

Pitfall

Unlinking the least recently used node but leaving its key in the map, which is why each node stores its own key. Also, put on an existing key must update and move that node, not add a duplicate node or trigger an eviction.

Solutions

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); // most recently used side
    private final Node tail = new Node(0, 0); // least recently used side

    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);
        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;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        node = new Node(key, value);
        map.put(key, node);
        addToFront(node);
    }

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

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

class Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.head = Node()  # most recently used side
        self.tail = Node()  # least recently used side
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._add_to_front(node)

    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node