146. LRU Cache

At a Glance

Topic: Hash Table
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 146

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache....

Approach & Solution Steps

Brute force — array + linear scan for LRU — O(n) per op.
Better — map + slice — removals still O(n).
Optimal — O(1) average — map key -> node, DLL nodes near head are MRU, near tail are LRU.

Optimal JS Solution

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

class LRUCache {
	constructor(capacity) {
		this.capacity = capacity;
		this.data = new Map();
		this.head = new LRUNode();
		this.tail = new LRUNode();
		this.head.next = this.tail;
		this.tail.prev = this.head;
	}

	add(node) {
		node.prev = this.head;
		node.next = this.head.next;
		this.head.next.prev = node;
		this.head.next = node;
	}

	remove(node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
	}

	get(key) {
		if (!this.data.has(key)) {
			return -1;
		}
		const node = this.data.get(key);
		this.remove(node);
		this.add(node);
		return node.value;
	}

	put(key, value) {
		if (this.data.has(key)) {
			const node = this.data.get(key);
			node.value = value;
			this.remove(node);
			this.add(node);
			return;
		}
		const node = new LRUNode(key, value);
		this.data.set(key, node);
		this.add(node);
		if (this.data.size > this.capacity) {
			const lru = this.tail.prev;
			this.remove(lru);
			this.data.delete(lru.key);
		}
	}
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.