LRU Cache

DESIGN · MEDIUM

The problem

Design a fixed-capacity cache supporting get(key) and put(key, value), both ideally O(1). When the cache is full and a new key is inserted, evict the least-recently-used entry — the one that hasn’t been read or written the longest.

Solution 1: Brute force — a plain array

Keep entries in one array, ordered from least-recently-used (front) to most-recently-used (end). Every get or put that touches an existing key has to scan the array to find it, then move it to the end.

Interactive visualization

capacity = 2 — operations: put/get sequence traced step by step

Press play to run through the cache operations.

Step 0 / 17

This animation traces the exact sequence verified above, capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4).

The code

class LRUCacheArray {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = []; // [key, value] pairs, front = LRU, end = MRU
  }
  get(key) {
    const idx = this.cache.findIndex(([k]) => k === key);
    if (idx === -1) return -1;
    const [, value] = this.cache[idx];
    this.cache.splice(idx, 1);
    this.cache.push([key, value]);
    return value;
  }
  put(key, value) {
    const idx = this.cache.findIndex(([k]) => k === key);
    if (idx !== -1) this.cache.splice(idx, 1);
    this.cache.push([key, value]);
    if (this.cache.length > this.capacity) this.cache.shift();
  }
}

Line by line:

findIndex is the O(n) cost — every get/put on an existing key scans from the front.
get splices the found entry out, then pushes it back at the end — that’s what marks it most-recently-used.
put on an existing key removes the old entry first so the fresh push doesn’t leave a stale duplicate.
this.cache.shift() evicts index 0 — by construction, the entry that’s been sitting at the front longest without being touched.

Complexity

Operation	Time	Space
get	O(n)	O(capacity)
put	O(n)

Solution 2: Optimal — Map + doubly linked list

Keep a doubly linked list ordered by recency (most-recently-used near a HEAD sentinel, least-recently-used near a TAIL sentinel), plus a Map from key straight to its list node. The Map turns “find this key” from an O(n) scan into an O(1) lookup; the linked list turns “move this node to the front” and “remove the last real node” into O(1) pointer updates.

Interactive visualization

capacity = 2 — same operation sequence as the brute-force solution, but with O(1) lookup and move

Press play to run through the cache operations.

Step 0 / 17

Same operation sequence as Solution 1 — watch the front of the chain track “most recently used” without ever scanning.

The code

class DListNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new DListNode(null, null); // sentinel, most-recent side
    this.tail = new DListNode(null, null); // sentinel, least-recent side
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _insertAtFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._insertAtFront(node);
    return node.value;
  }
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this._remove(node);
      this._insertAtFront(node);
      return;
    }
    const node = new DListNode(key, value);
    this.map.set(key, node);
    this._insertAtFront(node);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Line by line:

Two sentinel nodes (head, tail) remove every edge case around an empty list or a size-1 list — there’s always a real prev/next to link against.
_remove only needs the node itself (not a predecessor lookup) because every real node’s prev/next pointers are always kept valid.
this.map.has(key) is the O(1) replacement for the array solution’s findIndex — direct hash lookup instead of a scan.
Eviction reads this.tail.prev — with the sentinel tail, that’s always the real least-recently-used node, never undefined.

Complexity

Operation	Time	Space
get	O(1)	O(capacity)
put	O(1)

Complexity comparison

Solution	get	put	Space
Brute force (array)	O(n)	O(n)	O(capacity)
Optimal (Map + doubly linked list)	O(1)	O(1)	O(capacity)

Interview corner

Q: Why not just use a Map with a “last accessed” timestamp instead of a linked list?

You could track recency that way.
But finding the least-recently-used entry to evict would still require scanning every entry’s timestamp — O(n), defeating the whole point.
The linked list is what makes finding the LRU entry O(1), not just looking up a key by name.

Q: How would you extend this to LFU (Least Frequently Used) instead of LRU?

Track a use-count per key instead of (or alongside) recency.
Evict the lowest count, breaking ties by recency.
⚠ Trap: don’t casually claim “just change what gets evicted” — LFU Cache is a genuinely harder, separate LeetCode problem that needs a frequency-bucketed structure to stay O(1); it’s not a small tweak to this class.

Q: What should happen if capacity is 0?

get should always return -1.
put should never actually retain anything.
↳ Common follow-up: trace it through the code above — a put at capacity 0 inserts a node and then immediately evicts it for being over capacity, which happens to produce correct behavior. Worth confirming out loud with the interviewer that capacity 0 is an input they actually want handled, rather than silently assuming it.

Trick question — what does this log?

const cache = new LRUCache(2);
cache.put(1, 1);
const detachedGet = cache.get;
console.log(detachedGet(1));

Answer: it throws — TypeError: Cannot read properties of undefined (reading 'map').
Class methods aren’t auto-bound in JavaScript — this is only set correctly when a method is called as a property of its object (cache.get(1)).
detachedGet is called with no receiver, so inside get, this is undefined — and this.map.has(key) crashes immediately.
⚠ Trap: this is why libraries that hand out callbacks (array.map(cache.get), event handlers, etc.) either bind the method first (cache.get.bind(cache)) or use an arrow-function wrapper — passing a bare method reference silently loses its this.

Quiz

1. Why is the array-based solution O(n) per operation?

Arrays require sorting before every access
It isn’t — array access is always O(1)
get/put both need findIndex, an O(n) scan, to locate the key

Explanation: Both get and put need to locate a key first, and a plain array has no faster way to do that than findIndex — an O(n) linear scan in the worst case.

2. What two operations does the doubly linked list make O(1) that an array can’t?

Sorting the whole list by key
Removing a node from anywhere, and inserting a node at the front
Searching for a value directly, without a Map

Explanation: A doubly linked list makes both removing a node from anywhere and inserting a node at the front O(1), because every node holds direct pointers to its neighbors — no shifting or scanning required, unlike an array.

3. Why is a Map required in addition to the doubly linked list?

The Map is what enforces the capacity limit
It isn’t required — the linked list alone is already O(1)
Without it, finding a node by key would still require an O(n) list walk

Explanation: The linked list alone can’t jump to a key’s node without walking from head or tail — that’s still O(n). The Map is what supplies the O(1) key-to-node lookup that makes the whole design fast.

4. When the cache is full and a new key is inserted, which node gets evicted?

The node just after the HEAD sentinel
A randomly chosen node
The node just before the TAIL sentinel — the least-recently-used entry

Explanation: tail.prev is always the real node sitting closest to the TAIL sentinel — by construction, that’s the least-recently-used entry, since every access moves a node to the front instead.

5. Why does get() also count as “using” a key for LRU purposes?

get() resets the cache’s capacity counter
It doesn’t — only put() affects eviction order
LRU tracks recency of access, and get() moves the node to the front just like put() does

Explanation: LRU tracks recency of access, and get() moves the node to the front exactly like put() does, so a recently-read key isn’t the next one evicted just because it wasn’t recently written.