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.

Additional information

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

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

Brute Force (Hash Map + List)

Intuition

To implement a cache, we need a way to store key-value pairs and a way to track the history of when those keys were used.
The simplest approach is to use a Hash Map (Dictionary) to store the actual data, and a standard List (Array) to keep track of the usage order. Every time a key is accessed or inserted, we append it to the end of the List. If it was already in the List, we have to find it and move it to the end. The front of the list will always represent the Least Recently Used item.

Algorithm

1. Initialize a cache dictionary and an order list.
2. Get: Check if the key exists in cache. If it does, find its index in the order list, remove it (pop), and append it back to the end of the list to mark it as most recently used. Return the value.
3. Put: Check if the key exists. If it does, update its value in cache and move it to the end of the order list. If it doesn't exist, append it to order and add to cache. Finally, if the length of order exceeds capacity, pop(0) the first element from order (the LRU) and delete that key from the cache.

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.order = []

    def get(self, key: int) -> int:
        if key in self.cache:
            # Move the accessed key to the end (Most Recently Used)
            self.order.remove(key)
            self.order.append(key)
            return self.cache[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update value and move to Most Recently Used
            self.cache[key] = value
            self.order.remove(key)
            self.order.append(key)
        else:
            # Add new key
            self.cache[key] = value
            self.order.append(key)
            # Evict if over capacity
            if len(self.order) > self.capacity:
                lru_key = self.order.pop(0)
                del self.cache[lru_key]

Time & Space Complexity

• Time complexity: O(N) for both get and put.
  • Reason: While dictionary lookups are O(1), finding an element in a standard Python list (self.order.remove(key)) and popping from the front (self.order.pop(0)) requires shifting elements in memory, which takes linear O(N) time. This fails the strict O(1) requirement.
• Space complexity: O(C) where C is the capacity.

Hash Map + Doubly Linked List - Optimal

Intuition

To achieve strict O(1) time complexity, we must abandon the standard array. We need a data structure that allows us to remove an item from the middle and insert it at the end instantly.

A Doubly Linked List is perfectly suited for this. If we know the exact memory address of a Node, we can detach it from its neighbors and reattach it somewhere else in O(1) time. By using a Hash Map that maps keys directly to these Node objects, we get the best of both worlds: O(1) lookups from the Hash Map, and O(1) reordering from the Doubly Linked List.

We will use two "dummy" nodes (left and right) to represent the absolute boundaries of our cache. left.next will always point to our Least Recently Used node, and right.prev will always point to our Most Recently Used node.

Algorithm

1. Define a Node class with key, val, prev, and next pointers.
2. In __init__, set up the capacity, the Hash Map, and the two dummy nodes connected to each other (left <-> right).
3. Create two internal helper functions:
   • remove(node): detaches a node from the linked list by connecting its prev to its next.
   • insert(node): attaches a node right before the right dummy node (marking it as MRU).
4. Get: If the key is in the map, grab the node. Call remove(node) and insert(node) to refresh its status as MRU. Return its value.
5. Put: If the key exists, call remove(node) so we can replace it. Create a new Node, call insert(node), and map it in the dictionary. If length > capacity, grab the LRU node (self.left.next), call remove(lru), and delete it from the dictionary.

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 = {}  # Map key to Node
        
        # Dummy nodes to prevent edge-case null pointer checks
        self.left = Node()  # LRU boundary
        self.right = Node() # MRU boundary
        self.left.next = self.right
        self.right.prev = self.left

    def remove(self, node: Node) -> None:
        """Remove an existing node from the linked list."""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def insert(self, node: Node) -> None:
        """Insert node at the rightmost position (Most Recently Used)."""
        prev_mru = self.right.prev
        prev_mru.next = node
        self.right.prev = node
        node.prev = prev_mru
        node.next = self.right

    def get(self, key: int) -> int:
        if key in self.cache:
            # Refresh node as Most Recently Used
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
            
        # Create and insert new node
        new_node = Node(key, value)
        self.cache[key] = new_node
        self.insert(new_node)
        
        # Check capacity bounds
        if len(self.cache) > self.capacity:
            # Evict from the left (Least Recently Used)
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

Time & Space Complexity

• Time complexity: O(1) for both get and put.
  • Reason: Dictionary lookups take O(1) time. Thanks to the Doubly Linked List, removing and inserting nodes only requires updating a few pointer references, which is strictly O(1) regardless of cache size.
• Space complexity: O(C) where C is the capacity.
  • Reason: We store at most capacity number of nodes in both the Hash Map and the Linked List.