0146.LRU Cache

• Link: 146. LRU Cache - Medium
• Track: NeetCode150

Question

Restate the problem

• Put: (key, val), no return
• Get: give key, return val if no key, return -1
• Requirement:
  • Both operations in O(1) average time.
  • No duplicate key

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	HashMap + Doubly Linked List	- get: $O(1)$ - put: $O(1)$	$O(Capcity)$

Method 1 - HashMap + Doubly Linked List

Key idea:

• HashMap cache: cache[key] = node for O(1) lookup
• Doubly Linked List to maintain recency order
• Most recently used (MRU) near head; Least recently used (LRU) near tail
• Use two sentinel nodes head and tail to avoid edge-case pointer handling.

Approach

• _remove(node): Detach a node from the linked list by updating its neighbors.
• _add(node): Insert a node right after head, marking it as most recently used.
• get(key)
  1. If key is not in cache, return -1.
  2. Otherwise:
     • Retrieve the node from the hashmap.
     • Move it to the front of the list (_remove then _add) because it was recently used.
     • Return the node’s value.
• put(key, value)
  1. If key already exists:
     • Update the node’s value.
     • Move it to the front (MRU).
  2. If key does not exist:
     • Create a new node.
     • Insert it at the front.
     • Add it to the hashmap.
  3. If the cache size exceeds capacity:
     • Remove the LRU node (tail.prev).
     • Delete it from the hashmap.

Complexity

• Time Complexity: O(1)
• Space Complexity: O(1)

Code

class Node:
    def __init__(self, key, val, prev = None, next = None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next
 
class LRUCache:
 
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}                 # {key: Node}
 
        self.head = Node(key = -1, val = -1)
        self.tail = Node(key = -1, val = -1)
        self.head.next = self.tail      # ll: head -> tail
        self.tail.prev = self.head
 
    def _remove(self, node):            # ll: head -> node -> tail
        prev = node.prev
        nxt = node.next
 
        prev.next = nxt
        nxt.prev = prev
 
    def _add(self, node):               # ll: head -> node -> tail
        nxt = self.head.next
 
        node.prev = self.head
        node.next = nxt
        
        self.head.next = node
        nxt.prev = node
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        val = node.val
        
        self._remove(node)
        self._add(node)
        return val
 
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
        
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add(new_node)
 
        if len(self.cache) > self.capacity:
            r_node = self.tail.prev
            r_key = r_node.key
            self._remove(r_node)
            del self.cache[r_key]

---

Mistake

• Node include key for future delete