LRU Cache

Examples

Input: capacity = 2; put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output: -, -, 1, -, -1, -, -1, 3, 4

put(3,3) evicts key 2 (2 was the least recently used at that point, since key 1 had just been touched by get(1)). put(4,4) then evicts key 1 for the same reason.

Input: capacity = 1; put(1,1); get(1); put(2,2); get(1); get(2)
Output: -, 1, -, -1, 2

With capacity 1, inserting key 2 always evicts whatever key was there before.

Constraints

• 1 <= capacity <= 3000

• 0 <= key, value <= 10^4

• At most 2 * 10^5 total calls to get and put.

Approach

A simple first attempt: keep the cache as a plain list of key-value pairs. On get, scan the list for the key (moving it to the "most recent" end if found); on put, scan the list similarly, and if the cache is full, drop the entry at the "least recent" end. This is correct, but scanning and reordering the list costs time proportional to how many entries are currently cached.

The constant-time version pairs two structures: a hash map from key to a node, and a doubly linked list threading all the nodes together in usage order (most recently used at one end, least recently used at the other). The hash map gives instant access to any node by key; the doubly linked list lets you unlink that exact node and reinsert it at the "most recent" end in O(1), since removing or inserting next to a node you already hold a reference to never requires scanning anything. Eviction is then just "remove whatever sits at the least-recent end."

Solutions

Brute Force — Array of Pairs

Keep the cache as an array of {key, value} pairs, ordered from least recently used (front) to most recently used (back). Both get and put search the array for the key linearly; a hit is spliced out and pushed onto the back to mark it as freshly used. When capacity is exceeded, the pair at the front (the least recently used one) is dropped.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.items = []; // ordered least-recently-used (front) to most-recently-used (back)
  }

  get(key) {
    const index = this.items.findIndex((item) => item.key === key);
    if (index === -1) return -1;

    const [item] = this.items.splice(index, 1);
    this.items.push(item); // now the most recently used
    return item.value;
  }

  put(key, value) {
    const index = this.items.findIndex((item) => item.key === key);
    if (index !== -1) {
      this.items.splice(index, 1);
    } else if (this.items.length === this.capacity) {
      this.items.shift(); // evict the least recently used
    }
    this.items.push({ key, value });
  }
}

Time: O(n) per get/put, where n is the number of entries currently cached · Space: O(capacity)

Optimal — Doubly Linked List + Hash Map

Maintain a doubly linked list of nodes ordered by recency, with a permanent dummy head (the most-recently-used side) and a permanent dummy tail (the least-recently-used side), plus a hash map from key to its node in that list.

get: look the node up directly in the map. If found, unlink it from wherever it currently sits and reinsert it right after the dummy head (marking it freshly used), then return its value.

put: if the key already has a node, update its value and move it to the front the same way. Otherwise, if the cache is full, remove the node right before the dummy tail (the true least-recently-used entry) and delete it from the map; then create a new node for the key and insert it at the front.

Every step here — lookup, unlink, and insert-at-front — takes constant time, because the map gives a direct node reference and the doubly linked list never needs to scan to remove or insert next to a node it already holds.

class Node {
  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(); // key -> Node

    // Dummy sentinels: head.next is most recently used, tail.prev is least recently used.
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    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;
    }

    if (this.map.size === this.capacity) {
      const leastRecentlyUsed = this.tail.prev;
      this._remove(leastRecentlyUsed);
      this.map.delete(leastRecentlyUsed.key);
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this._insertAtFront(node);
  }
}

Time: O(1) for both get and put · Space: O(capacity)