34. LRU Cache

Design a fixed-size key-value cache that evicts the least recently used entry when it runs out of room.

Implement the LRUCache class:

LRUCache(capacity) creates an empty cache that can hold at most capacity entries.
get(key) returns the value stored for key, or -1 if the key is not in the cache.
put(key, value) stores value under key, replacing any existing value. If this adds a new key and the cache now holds more than capacity entries, remove the entry that was used least recently.

Both a successful get and any put count as a use of that key. A get for a missing key changes nothing. Both operations must run in O(1) average time.

Example 1

Input: ["LRUCache","put","put","get","put","get","get","put","put","get","get","get"]
[[2],[1,10],[2,20],[1],[3,30],[2],[3],[1,15],[4,40],[3],[1],[4]]
Output: [null,null,null,10,null,-1,30,null,null,-1,15,40]

Explanation: Reading key 1 makes key 2 the least recently used, so adding key 3 evicts key 2. Later, updating key 1 leaves key 3 as the oldest, and adding key 4 evicts it.

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls to get and put

💡 Hint 1

A hash map gives O(1) lookup, but it does not remember which key was used least recently. What structure can reorder items in O(1)?

💡 Hint 2

Keep the entries in a doubly linked list ordered by recency, and let the map point at the list nodes so you can unlink any entry instantly.

💡 Hint 3

Sentinel head and tail nodes remove the empty-list edge cases. In JavaScript, a Map already iterates in insertion order, which you can exploit.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Combine a hash map with a doubly linked list ordered by recency. The list runs from least recently used (just after a sentinel head) to most recently used (just before a sentinel tail), and the map sends each key to its list node. get looks the node up, unlinks it and re-inserts it before tail. put either updates an existing node and moves it the same way, or appends a new node; if that pushes the size past capacity, it removes the node right after head and deletes its key from the map. Every step touches a constant number of pointers.

In JavaScript, a Map iterates keys in insertion order, so deleting and re-setting a key moves it to the "most recent" end, and map.keys().next().value is the least recently used key. That gives the same O(1) behavior with much less code.

Time O(1) average per operationSpace O(capacity)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }
  put(key, value) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

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), tail = new Node(0, 0);

    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;
        unlink(node);
        append(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            unlink(node);
            append(node);
            return;
        }
        node = new Node(key, value);
        map.put(key, node);
        append(node);
        if (map.size() > capacity) {
            Node lru = head.next;
            unlink(lru);
            map.remove(lru.key);
        }
    }

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

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

class LRUCache {
  /** @param {number} capacity */
  constructor(capacity) {

  }

  /**
   * @param {number} key
   * @return {number}
   */
  get(key) {

  }

  /**
   * @param {number} key
   * @param {number} value
   * @return {void}
   */
  put(key, value) {

  }
}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit