LRU Cache

Problem

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.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

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

Solution

Approach 1: Hash Map + Doubly Linked List

The key insight is to combine a hash map (for O(1) access) with a doubly linked list (for O(1) removal/addition). The list maintains order with most recently used at the head.

Data structures:

Hash map: key → node reference
Doubly linked list: nodes ordered by recency (head = most recent, tail = least recent)

Implementation

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> node
        # Dummy head and tail for easier manipulation
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """Remove node from list"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node):
        """Add node right after head (most recent position)"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

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

        node = self.cache[key]
        # Move to head (mark as most recently used)
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing key
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_head(node)
        else:
            # Add new key
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_head(node)

            # Check capacity
            if len(self.cache) > self.capacity:
                # Remove least recently used (node before tail)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

Approach 2: Using OrderedDict

Python’s OrderedDict maintains insertion order and provides move_to_end() for O(1) reordering—essentially a built-in doubly linked list + hash map.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

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

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

Complexity Analysis

Time Complexity: O(1) for both get and put operations. Hash map provides O(1) lookup, and doubly linked list provides O(1) insertion/deletion.
Space Complexity: O(capacity), we store at most capacity nodes.

Key Insights

Two Data Structures: Hash map provides O(1) access to nodes, while doubly linked list maintains the order for O(1) eviction.
Doubly Linked Advantage: We need to remove nodes from arbitrary positions (when accessing) and from the tail (when evicting). Doubly linked list allows O(1) removal with a node reference.
Dummy Nodes: Using dummy head and tail nodes simplifies edge cases. We never have to check if the list is empty or handle special cases for head/tail.
Most Recent at Head: We add recently used nodes right after the head. The node before the tail is the least recently used and gets evicted first.
Access Updates Order: Both get and put make a key “recently used,” so we move its node to the head in both operations.
Store Key in Node: We store the key in the node so we can delete it from the hash map when evicting the LRU node.
Standard Library: Python’s OrderedDict implements the same hash map + doubly linked list structure internally, making Approach 2 equivalent but more concise.