LeetCode 146 - LRU Cache

LeetCode Problem 146

Difficulty: 🟡 Medium
Topics: Hash Table, Linked List, Design, Doubly-Linked List

Solution

Problem Understanding

The problem asks us to design an efficient cache that follows the Least Recently Used, or LRU, eviction policy. A cache stores a limited number of key-value pairs. When the cache reaches its maximum capacity and a new item must be inserted, the least recently used item should be removed first.

The class must support two operations:

• get(key) retrieves the value associated with a key
• put(key, value) inserts or updates a key-value pair

The important requirement is that both operations must run in average O(1) time complexity.

The phrase "least recently used" means that whenever a key is accessed through either get or put, it becomes the most recently used item. The item that has gone the longest without being accessed becomes the eviction candidate.

The input consists of a sequence of operations performed on the cache. Each operation either inserts data, updates data, or retrieves data. The output for each get operation is the corresponding value if the key exists, otherwise -1.

The constraints are important:

• Capacity is at most 3000
• Up to 2 * 10^5 operations may occur

A naive implementation that scans the cache to determine usage order would become too slow. Since there can be 200,000 operations, each operation must truly be constant time on average.

Several edge cases matter:

• Accessing a key that does not exist should return -1
• Updating an existing key should not increase cache size
• Accessing a key should refresh its usage status
• Inserting into a full cache should evict exactly one least recently used item
• A cache with capacity 1 is especially error-prone because every new insertion causes eviction

Approaches

Brute Force Approach

A straightforward implementation would use a hash map to store key-value pairs and a separate list to track usage order.

Whenever a key is accessed or updated, we move it to the end of the usage list. When eviction is needed, we remove the least recently used key from the front of the list.

The problem is that updating the usage order inside a normal list requires searching for the key first. Removing an arbitrary element from a list takes O(n) time because elements must be shifted.

For example:

• get(key) requires locating the key in the usage list and moving it
• put(key, value) may also require list updates and shifting

With up to 200,000 operations, this becomes inefficient.

Optimal Approach

The key insight is that we need two different capabilities simultaneously:

1. Fast key lookup
2. Fast insertion and removal from the usage order

A hash map provides O(1) average lookup time, while a doubly linked list provides O(1) insertion and deletion if we already have a pointer to the node.

We combine these two structures:

• Hash map: maps keys to linked list nodes
• Doubly linked list: maintains usage order

The linked list stores nodes in order from least recently used to most recently used.

Whenever a key is accessed:

• Remove its node from the list
• Move it to the tail

Whenever a new key is inserted:

• Add it to the tail
• If capacity is exceeded, remove the head node

This gives constant time operations for both get and put.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per operation	O(n)	List updates require scanning and shifting
Optimal	O(1) average per operation	O(n)	Hash map plus doubly linked list

Algorithm Walkthrough

1. Create a doubly linked list to track usage order.

The front of the list represents the least recently used item. The back represents the most recently used item. 2. Use dummy head and dummy tail nodes.

Dummy nodes simplify insertion and removal logic because we never need special handling for empty lists or single-element lists. 3. Create a hash map from keys to linked list nodes.

This allows direct access to any cache entry in constant time. 4. For the get(key) operation:

• Check whether the key exists in the hash map

• If not found, return -1

• Otherwise:

• Remove the node from its current position

• Move it to the end of the list because it was recently used

• Return the stored value

5. For the put(key, value) operation:

• If the key already exists:

• Update its value

• Move it to the end because it was recently used

• Otherwise:

• Create a new node

• Insert it at the end

• Add it to the hash map

6. After insertion, check capacity.

If the cache size exceeds capacity:

• Remove the least recently used node from the front
• Delete its key from the hash map

Why it works

The hash map guarantees constant-time access to nodes. The doubly linked list guarantees constant-time insertion and deletion once we have a node reference. The linked list always maintains correct usage order because every access moves a node to the tail. Therefore, the head of the list is always the least recently used item, which ensures correct eviction behavior.

Python Solution

class Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}

        self.head = Node()
        self.tail = Node()

        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        prev_node = node.prev
        next_node = node.next

        prev_node.next = next_node
        next_node.prev = prev_node

    def _insert_to_tail(self, node: Node) -> None:
        prev_tail = self.tail.prev

        prev_tail.next = node
        node.prev = prev_tail

        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        node = self.cache[key]

        self._remove(node)
        self._insert_to_tail(node)

        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value

            self._remove(node)
            self._insert_to_tail(node)
            return

        new_node = Node(key, value)

        self.cache[key] = new_node
        self._insert_to_tail(new_node)

        if len(self.cache) > self.capacity:
            lru_node = self.head.next

            self._remove(lru_node)
            del self.cache[lru_node.key]

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

The implementation begins with a Node class representing one cache entry inside the doubly linked list. Each node stores:

• The key
• The value
• A pointer to the previous node
• A pointer to the next node

The cache itself maintains:

• A hash map called cache
• A doubly linked list bounded by dummy head and tail nodes

The _remove helper detaches a node from the linked list in constant time by reconnecting its neighboring nodes.

The _insert_to_tail helper inserts a node directly before the dummy tail node, making it the most recently used item.

The get method checks whether the key exists. If it does, the node is moved to the tail because it was recently accessed.

The put method first handles updates for existing keys. Existing keys are refreshed and moved to the tail. For new keys, a node is inserted into both the hash map and linked list.

If capacity is exceeded, the least recently used node is always located immediately after the dummy head node. That node is removed from both the linked list and hash map.

Go Solution

type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

type LRUCache struct {
	capacity int
	cache    map[int]*Node
	head     *Node
	tail     *Node
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}

	head.next = tail
	tail.prev = head

	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     head,
		tail:     tail,
	}
}

func (this *LRUCache) remove(node *Node) {
	prevNode := node.prev
	nextNode := node.next

	prevNode.next = nextNode
	nextNode.prev = prevNode
}

func (this *LRUCache) insertToTail(node *Node) {
	prevTail := this.tail.prev

	prevTail.next = node
	node.prev = prevTail

	node.next = this.tail
	this.tail.prev = node
}

func (this *LRUCache) Get(key int) int {
	node, exists := this.cache[key]

	if !exists {
		return -1
	}

	this.remove(node)
	this.insertToTail(node)

	return node.value
}

func (this *LRUCache) Put(key int, value int) {
	if node, exists := this.cache[key]; exists {
		node.value = value

		this.remove(node)
		this.insertToTail(node)

		return
	}

	newNode := &Node{
		key:   key,
		value: value,
	}

	this.cache[key] = newNode
	this.insertToTail(newNode)

	if len(this.cache) > this.capacity {
		lruNode := this.head.next

		this.remove(lruNode)
		delete(this.cache, lruNode.key)
	}
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

The Go implementation follows the same design as the Python solution. One notable difference is explicit pointer handling through *Node. Go maps return both a value and a boolean existence flag, which is used to determine whether a key exists in the cache.

Unlike Python, Go does not have automatic None semantics. Instead, linked list pointers are handled explicitly with nil values, although the dummy head and tail nodes prevent most special-case pointer logic.

Worked Examples

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]]

Capacity = 2

We represent the linked list from left to right as:

LRU -> MRU

Operation	Cache State	Result
put(1,1)	1
put(2,2)	1 → 2
get(1)	2 → 1	1
put(3,3)	1 → 3	evict 2
get(2)	1 → 3	-1
put(4,4)	3 → 4	evict 1
get(1)	3 → 4	-1
get(3)	4 → 3	3
get(4)	3 → 4	4

Detailed reasoning:

After get(1), key 1 becomes most recently used, so key 2 becomes the least recently used.

When inserting 3, capacity would become 3, so key 2 is evicted.

Later, inserting 4 evicts key 1 because it is now the least recently used.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) average per operation	Hash map lookup and linked list updates are constant time
Space	O(capacity)	The cache stores at most capacity nodes

The hash map stores one entry per cache item, and the linked list stores the same nodes in usage order. Each operation performs only a constant number of pointer updates and hash map accesses, so both get and put run in average constant time.

Test Cases

# Example from problem statement
cache = LRUCache(2)

cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1  # recently used item

cache.put(3, 3)
assert cache.get(2) == -1  # key 2 should be evicted

cache.put(4, 4)
assert cache.get(1) == -1  # key 1 should be evicted
assert cache.get(3) == 3   # key 3 should remain
assert cache.get(4) == 4   # key 4 should remain

# Capacity 1 edge case
cache = LRUCache(1)

cache.put(1, 1)
assert cache.get(1) == 1  # value exists

cache.put(2, 2)
assert cache.get(1) == -1  # old key evicted
assert cache.get(2) == 2   # new key remains

# Updating existing key
cache = LRUCache(2)

cache.put(1, 1)
cache.put(1, 10)

assert cache.get(1) == 10  # value updated

# Access refreshes usage order
cache = LRUCache(2)

cache.put(1, 1)
cache.put(2, 2)

assert cache.get(1) == 1  # key 1 becomes most recent

cache.put(3, 3)

assert cache.get(2) == -1  # key 2 should be evicted
assert cache.get(1) == 1   # key 1 remains

# Missing key lookup
cache = LRUCache(2)

assert cache.get(99) == -1  # nonexistent key

# Multiple updates and evictions
cache = LRUCache(3)

cache.put(1, 1)
cache.put(2, 2)
cache.put(3, 3)

cache.get(1)
cache.put(4, 4)

assert cache.get(2) == -1  # key 2 evicted
assert cache.get(1) == 1
assert cache.get(3) == 3
assert cache.get(4) == 4

Test	Why
Basic example sequence	Verifies standard LRU behavior
Capacity = 1	Tests constant eviction behavior
Updating existing key	Ensures updates do not duplicate keys
Access refreshes usage	Verifies recency ordering
Missing key lookup	Confirms correct -1 handling
Multiple updates and evictions	Tests long operation sequences

Edge Cases

Capacity Equal to One

A cache with capacity 1 is a common source of bugs because every insertion after the first immediately triggers eviction. Some incorrect implementations accidentally retain stale nodes or fail to update usage order correctly.

This implementation handles the case naturally because insertion always checks whether the cache size exceeds capacity. If it does, the least recently used node is removed immediately.

Updating an Existing Key

Another common issue occurs when inserting a key that already exists. A buggy implementation might accidentally create duplicate nodes in the linked list or incorrectly increase cache size.

This solution first checks whether the key already exists in the hash map. If it does, the existing node's value is updated directly, and the node is moved to the tail without creating a new node.

Repeated Accesses to the Same Key

Repeatedly calling get on the same key should continuously refresh its recency status. Some incorrect solutions forget to move the node after access, causing recently used keys to be evicted incorrectly.

This implementation always removes and reinserts the accessed node at the tail, ensuring the linked list order always reflects true recency.

Accessing Nonexistent Keys

The cache must return -1 for keys that are not present. Incorrect implementations may accidentally dereference missing nodes or produce inconsistent behavior.

The hash map lookup safely checks key existence first. If the key is absent, the method immediately returns -1 without modifying the linked list.