#146 LRU Cache

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get and put operations, both running in $O(1)$ average time complexity.

Intuition

We need fast key lookup (hash map) and fast ordering updates (doubly linked list). The most recently used item goes to the head; the least recently used is at the tail, ready for eviction.

Approach

1. Use a Map which preserves insertion order in JavaScript.
2. On get, delete and re-insert the key to move it to the end (most recent).
3. On put, delete the key if it exists, then insert it. If capacity is exceeded, delete the first (oldest) key.

Solution

class LRUCache {
  private capacity: number;
  private cache: Map<number, number>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

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

  put(key: number, value: number): void {
    this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const oldest = this.cache.keys().next().value!;
      this.cache.delete(oldest);
    }
  }
}

Complexity Analysis