4.9.9 — LRU Cache

LeetCode 146 · Medium · ★ Blind 75

The problem

Design a cache with a fixed capacity supporting two operations, both in O(1):

• get(key) — return the value, or −1 if absent. This counts as using the key.
• put(key, value) — insert or update. If the cache is over capacity, evict the least recently used key.

LRUCache(2)
put(1,1); put(2,2)
get(1)      → 1        (1 is now the most recently used)
put(3,3)                (over capacity → evict 2, the least recently used)
get(2)      → -1

The Plain-English Breakdown

You are asked to build a system that acts like a browser tab manager. You can only have capacity number of tabs open. If you open a new tab and you're at the limit, the browser automatically closes the tab you haven't looked at in the longest time (Least Recently Used). If you click on an old tab, it refreshes and becomes the most recently used. Everything must happen instantly (O(1)).

Constraints to note:

• capacity is up to 3000.
• Calls to get and put can be up to 2 \times 10^5.
• Time limit is extremely tight, enforcing true O(1) average time.

Brute Force Analysis

A naive approach is to use a standard Array/List combined with a Hash Map, or just an Array of objects with timestamp properties.

• Why it fails: If you use an array and just keep it sorted by recency, every time you get an item, you have to find it, remove it, and shift all other elements down to put it at the front. Shifting an array takes O(N) time. With 200,000 calls, O(N) operations will result in a Time Limit Exceeded error. We absolutely need to be able to rip an item out of the middle of our ordering without shifting everything else.

The pattern

Two requirements pull in different directions:

• Find a key instantly. That is a hash map.
• Know which key was used longest ago, and move keys to the front instantly. A hash map cannot do this — it has no order.

Neither structure alone works, so use both, and let each cover the other's weakness.

• A hash map from key to node, giving O(1) lookup.
• A doubly linked list holding the nodes in use order, most recent at the front.

The map finds the node; the list knows the order. This combination is the answer, and being able to say why in one sentence is the whole point of the problem.

Why the list must be doubly linked

To move a node to the front you must first unlink it from where it is, and to unlink a node you need the node before it.

In a singly linked list, finding the previous node costs O(n) — you would have to walk from the head. A prev pointer makes it O(1). That is the entire justification, and it is the reason doubly linked lists exist at all.

Why two dummy nodes

Insertion at the front and removal at the back both have edge cases: an empty list, a single element, the node being at the boundary. Every one of them disappears if you put permanent sentinel nodes at both ends.

head ⇄ [most recent] ⇄ … ⇄ [least recent] ⇄ tail
 ↑                                            ↑
 dummy, never holds data              dummy, never holds data

Now every real node has a real neighbour on both sides, so unlinking is always the same two lines with no branches. This is the dummy-head idea from 4.9.2, applied at both ends.

The solution

Python

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


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                      # key → Node
        self.head = Node()                 # dummy: most recent side
        self.tail = Node()                 # dummy: least recent side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)                 # it was just used…
        self._add_front(node)              # …so it moves to the front
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])    # drop the old node entirely

        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

        if len(self.map) > self.cap:
            lru = self.tail.prev           # the node just before the tail dummy
            self._remove(lru)
            del self.map[lru.key]          # ← this is why nodes store their key

TypeScript

class LNode {
  key = 0; val = 0;
  prev: LNode | null = null;
  next: LNode | null = null;
  constructor(key = 0, val = 0) { this.key = key; this.val = val; }
}

class LRUCache {
  private cap: number;
  private map = new Map<number, LNode>();
  private head = new LNode();
  private tail = new LNode();

  constructor(capacity: number) {
    this.cap = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private remove(node: LNode) {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private addFront(node: LNode) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.remove(node);
    this.addFront(node);
    return node.val;
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) this.remove(existing);

    const node = new LNode(key, value);
    this.map.set(key, node);
    this.addFront(node);

    if (this.map.size > this.cap) {
      const lru = this.tail.prev!;
      this.remove(lru);
      this.map.delete(lru.key);
    }
  }
}

The node stores its key as well as its value, and that is not redundant. When evicting, you find the node from the list — but you must also delete its entry from the map, and for that you need the key. Without it you would have to search the map for the node, which is O(n) and destroys the whole design. This is the detail most people miss.

get must reorder. A read counts as a use. Forgetting this makes it a least-recently-inserted cache, which passes some tests and fails the ones that matter.

On put of an existing key, the old node is removed and a fresh one inserted at the front. Updating the value in place and moving the node would work equally well and allocates less.

ELI5 Analogy: Think of a bookshelf where you only have room for 5 books. Every time you read a book, you take it out and slide it onto the far left end. The books get pushed rightwards over time. The book on the far right is the one you haven't touched in ages. When you buy a new book, you throw away the far-right book to make room, and place the new one on the far left. The Doubly Linked List is the shelf (allowing you to pull a book from anywhere without shifting the others, you just connect the books next to it), and the Hash Map is a magic catalog that tells you exactly where any book is sitting.

Code Walkthrough

1. The Node: We define a LNode class that holds key, val, prev, and next. It is a doubly linked list node.
2. The Constructor: We initialize cap, a map to store key -> LNode, and two dummy nodes: head (most recent) and tail (least recent). We wire head.next = tail and tail.prev = head.
3. Helper: remove: Rips a node out of the list by wiring its prev and next neighbours directly to each other.
4. Helper: addFront: Inserts a node exactly between head and head.next. This makes it the most recently used.
5. The get method: We look up the key in the map. If missing, return -1. If found, we must mark it as recently used! We call remove(node) then addFront(node). We return node.val.
6. The put method: If the key already exists, we find it and remove it entirely. Then we create a new node with the potentially updated value, put it in the map, and addFront it.
7. Eviction: If map.size > cap, we must evict. The LRU node is ALWAYS exactly tail.prev. We find it, remove(lru) from the list, and crucially, map.delete(lru.key) to wipe it from the hash map.

Complexity

O(1) for both operations. Every step is a map lookup or a fixed number of pointer assignments.

O(capacity) space.

Derivation:

• Time Complexity: O(1) for both get and put. Let's trace it: Hash map lookups (map.get, map.set, map.delete) operate in O(1) average time. The remove and addFront helpers execute exactly four pointer reassignments each, with no loops. Therefore, all operations execute in constant time.
• Space Complexity: O(C) where C is the capacity. The Hash Map stores at most C key-value pairs. The Doubly Linked List stores at most C + 2 nodes (including the dummies). Space scales linearly with the cache capacity.

The shortcut, and why to know both

Python has OrderedDict, which is a hash map that remembers insertion order and can move a key to either end in O(1):

from collections import OrderedDict

class LRUCache(OrderedDict):
    def __init__(self, capacity):
        self.cap = capacity

    def get(self, key):
        if key not in self: return -1
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        if key in self: self.move_to_end(key)
        self[key] = value
        if len(self) > self.cap:
            self.popitem(last=False)

JavaScript's Map also preserves insertion order, so map.keys().next().value gives the oldest key and re-inserting moves a key to the end.

Both are correct and both are how you would write it in production. In an interview, write the manual version — the question is testing whether you can build the structure, and OrderedDict is a hash map with a doubly linked list inside it, doing exactly what you would have done. Say that, then offer the shortcut.

Where this goes next

• LFU Cache (LeetCode 460, worked in full in 4.9.12) — evict the least frequently used instead. Now you need a map from frequency to a list of keys at that frequency, plus a running minimum frequency. Considerably harder, and it is the natural follow-up.
• Real caches — Redis, your CPU's cache, a database buffer pool, and your browser's HTTP cache all face this decision. Most do not use true LRU, because maintaining it costs memory and locking; they approximate it with clock or second-chance algorithms. Chapter 10.14 covers eviction policies properly, and Chapter 2.5 covers the operating system's page replacement.

The rule: when one structure cannot give you both fast lookup and useful ordering, combine two and keep them in step. That combination is the recurring idea; the list is not special.

What the interviewer will push on

"Why a doubly linked list?" Unlinking a node needs its predecessor, and only a prev pointer gives that in O(1).

"Why does the node store its key?" To delete the map entry when evicting.

"Does get change the order?" Yes — a read is a use.

"How would you make it thread-safe?" The map and the list must stay consistent, so both updates go inside one lock. A per-structure lock lets another thread see a node in the map that has already left the list. Chapter 2.4.

"How is a real cache different?" True LRU costs a pointer update on every read, which is expensive under contention. Production caches approximate it. Saying this shows you know the difference between an exercise and a system.

One thing to volunteer: state the design in one sentence before writing anything. "A hash map for O(1) lookup, and a doubly linked list for O(1) reordering, with the map pointing at list nodes." Then build it.

Next: 4.9.10 Merge K Sorted Lists — the merge from 4.9.2 scaled up, and the first appearance of a heap.