LRU Cache

The problem

Design `LRUCache(capacity)` with `get(key)` returning the value for `key` or `-1` if it's absent, and `put(key, value)` inserting or updating a key — evicting the least recently used entry if the cache is over capacity after the insert. Both operations must run in O(1) average time, which rules out re-scanning the whole cache to find 'the oldest' on every call.

'Recently used' updates on both reads and writes: calling `get` on a key, or `put`-ing a value for an existing key, counts as using it and must push it to the back of the eviction order — only keys nobody has touched drift toward eviction.

The approach

A `Map` is the right primitive here because JS guarantees it iterates in insertion order, and `.delete()` followed by `.set()` re-adds a key at the end of that order rather than leaving it at its old position. So 'least recently used' is just 'the first entry in insertion order' — no separate ordering structure needed.

`get` deletes and re-inserts the key it just read, carrying its existing value, before returning it — so a read counts as a use and the key moves to the most-recently-used end. A miss short-circuits with `-1` before any of that runs.

`put` deletes the key first if it already exists, so the `.set()` that follows re-adds it at the end instead of leaving it in its old position. Only when the key is new *and* the cache is already at capacity does it evict — reading the oldest key out of `this.cache.keys().next().value` before inserting the new one.

The solution

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size === this.capacity) {
      const lru = this.cache.keys().next().value;
      this.cache.delete(lru);
    }
    this.cache.set(key, value);
  }
}

Time O(1)Space O(n)