LeetCode 146: LRU Cache Solution in Python Explained

Problem Statement

In LeetCode 146, you’re tasked with implementing an LRUCache class:

• LRUCache(int capacity): Initializes the cache with a positive capacity.
• int get(int key): Returns the value of the key if it exists, otherwise -1, and marks it as recently used.
• void put(int key, int value): Updates or inserts the key-value pair, evicting the least recently used item if the cache is full.

Operations must run in O(1) time. This differs from tree traversal like LeetCode 145: Binary Tree Postorder Traversal, focusing on data structure design rather than traversal.

Constraints

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

Example

Let’s see a case:

Copy codeInput:
["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:
<ul>
<li>LRUCache(2): Capacity 2.</li>
<li>put(1,1): Cache = [(1,1)].</li>
<li>put(2,2): Cache = [(2,2),(1,1)].</li>
<li>get(1): Returns 1, Cache = [(1,1),(2,2)].</li>
<li>put(3,3): Evicts 2, Cache = [(3,3),(1,1)].</li>
<li>get(2): Returns -1 (not found).</li>
<li>put(4,4): Evicts 1, Cache = [(4,4),(3,3)].</li>
<li>get(1): Returns -1.</li>
<li>get(3): Returns 3, Cache = [(3,3),(4,4)].</li>
<li>get(4): Returns 4, Cache = [(4,4),(3,3)].</li>
</ul>

This shows we’re managing a cache with LRU eviction.

Understanding the Problem

How do you solve LeetCode 146: LRU Cache in Python? We need a data structure supporting O(1) get and put, tracking usage order, and evicting the least recently used item. For capacity 2, put(1,1), put(2,2), get(1), put(3,3) evicts 2, and so on. This isn’t a list reordering task like LeetCode 143: Reorder List; it’s about cache management. We’ll use: 1. Doubly Linked List with Hash Map: O(n) time, O(1) space for operations—our best solution. 2. OrderedDict: O(n) time, O(1) space for operations—an alternative.

Let’s dive into the best solution.

Best Solution: Doubly Linked List with Hash Map Approach

Explanation

Doubly Linked List with Hash Map uses:

• A doubly linked list to maintain order (head = most recent, tail = least recent), with O(1) node movement.
• A hash map to map keys to nodes for O(1) access.

For get, fetch the node via the map, move it to the head, and return its value. For put, update or insert the node at the head, evicting the tail if full. This is the best solution due to its O(1) time complexity for both operations, O(capacity) space, and efficient in-place updates, making it optimal and robust.

For capacity 2:

• put(1,1): [(1,1)].
• put(2,2): [(2,2),(1,1)].
• get(1): [(1,1),(2,2)].
• put(3,3): [(3,3),(1,1)].

Step-by-Step Example

Example: ["LRUCache","put","put","get","put","get","put","get","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

• Step 1: LRUCache(2):
• capacity = 2, cache = {{, list = dummy_head <-> dummy_tail.
• Step 2: put(1,1):
• Add (1,1), list = head<->(1,1)<->tail, cache = {1:(1,1){.
• Step 3: put(2,2):
• Add (2,2), list = head<->(2,2)<->(1,1)<->tail, cache = {1:(1,1), 2:(2,2){.
• Step 4: get(1):
• Move (1,1) to head, list = head<->(1,1)<->(2,2)<->tail, return 1.
• Step 5: put(3,3):
• Full, remove (2,2), add (3,3), list = head<->(3,3)<->(1,1)<->tail, cache = {1:(1,1), 3:(3,3){.
• Step 6: get(2):
• Not found, return -1.
• Step 7: put(4,4):
• Remove (1,1), add (4,4), list = head<->(4,4)<->(3,3)<->tail, cache = {3:(3,3), 4:(4,4){.
• Step 8-10: get(1) → -1, get(3) → 3, get(4) → 4.

How the Code Works (Doubly Linked List with Hash Map) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

class LRUCache:
    def __init__(self, capacity: int):
        # Line 1: Initialize capacity and cache
        self.capacity = capacity
        # Max size (e.g., 2)
        self.cache = {{
        # Maps keys to nodes (e.g., {{)

        # Line 2: Initialize dummy nodes
        self.head = Node()
        # Dummy head for most recent
        self.tail = Node()
        # Dummy tail for least recent
        self.head.next = self.tail
        # Link head to tail
        self.tail.prev = self.head
        # Link tail to head

    def _add_node(self, node: Node):
        # Line 3: Add node after head (most recent)
        node.prev = self.head
        # e.g., node.prev = head
        node.next = self.head.next
        # e.g., node.next = (1,1)
        self.head.next.prev = node
        # e.g., (1,1).prev = node
        self.head.next = node
        # e.g., head.next = node

    def _remove_node(self, node: Node):
        # Line 4: Remove node from list
        node.prev.next = node.next
        # e.g., head.next = tail
        node.next.prev = node.prev
        # e.g., tail.prev = head

    def _move_to_head(self, node: Node):
        # Line 5: Move node to most recent
        self._remove_node(node)
        # Remove from current position
        self._add_node(node)
        # Add after head

    def get(self, key: int) -> int:
        # Line 6: Get value for key
        if key in self.cache:
            # If key exists (e.g., 1)
            node = self.cache[key]
            # Fetch node (e.g., (1,1))
            self._move_to_head(node)
            # Move to most recent (e.g., head<->(1,1)<->...)
            return node.value
            # Return value (e.g., 1)
        return -1
        # Key not found

    def put(self, key: int, value: int) -> None:
        # Line 7: Update or insert key-value pair
        if key in self.cache:
            # If key exists (e.g., 1)
            node = self.cache[key]
            # Fetch node (e.g., (1,1))
            node.value = value
            # Update value (e.g., 1)
            self._move_to_head(node)
            # Move to head
        else:
            # New key (e.g., 3)
            new_node = Node(key, value)
            # Create node (e.g., (3,3))
            self.cache[key] = new_node
            # Add to cache (e.g., {3:(3,3){)
            self._add_node(new_node)
            # Add to list (e.g., head<->(3,3)<->...)
            if len(self.cache) > self.capacity:
                # If over capacity (e.g., 3 > 2)
                lru_node = self.tail.prev
                # Least recent (e.g., (1,1))
                self._remove_node(lru_node)
                # Remove from list
                del self.cache[lru_node.key]
                # Remove from cache

This detailed breakdown clarifies how the doubly linked list with hash map manages the LRU cache.

Alternative: OrderedDict Approach

Explanation

OrderedDict uses Python’s collections.OrderedDict, which maintains insertion order and supports O(1) operations for moving items to the end (most recent) and popping the first item (least recent). It’s a practical alternative, simple with O(1) time for get and put, but relies on a built-in structure rather than a custom implementation.

For capacity 2:

• put(1,1): {1:1{.
• put(2,2): {1:1, 2:2{.
• get(1): {2:2, 1:1{.
• put(3,3): {1:1, 3:3{.

Step-by-Step Example (Alternative)

For the same example:

• Step 1: OrderedDict(), capacity 2.
• Step 2: put(1,1): {1:1{.
• Step 3: put(2,2): {1:1, 2:2{.
• Step 4: get(1): Move 1, {2:2, 1:1{, return 1.
• Step 5: put(3,3): Pop 2, {1:1, 3:3{.

How the Code Works (OrderedDict)

Copy codefrom collections import OrderedDict

class LRUCacheOrderedDict:
    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
        value = self.cache.pop(key)
        self.cache[key] = value
        return value

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

Complexity

• Doubly Linked List with Hash Map:
• Time: O(1) – get/put operations.
• Space: O(capacity) – list and map.
• OrderedDict:
• Time: O(1) – get/put operations.
• Space: O(capacity) – dictionary.

Efficiency Notes

Doubly Linked List with Hash Map is the best solution with O(1) time and O(capacity) space, offering a custom, flexible implementation—OrderedDict matches complexity using a built-in tool, making it simpler but less illustrative of core concepts.

Key Insights

• LRU: Track usage order.
• Doubly Linked: O(1) moves.
• OrderedDict: Built-in order.

Additional Example

For ["LRUCache","put","put","get"], [[1],[1,1],[2,2],[1]]:

• Goal: [null,null,null,1].
• DLL: Evicts 1 for 2, returns 1.

Edge Cases

• Capacity 1: [1], put(2,2) → [2].
• Single Call: get(1) → -1.
• Full Cache: Evicts correctly.

Both solutions handle these well.

Final Thoughts

LeetCode 146: LRU Cache in Python is a classic data structure challenge. The Doubly Linked List with Hash Map solution excels with its efficiency and clarity, while OrderedDict offers a concise alternative. Want more? Try LeetCode 141: Linked List Cycle for list basics or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 146 on LeetCode with the example above, aiming for the correct sequence—test your skills now!