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.

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

Thinking Process

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.
  • Slow/fast pointers find middle or detect cycles in one pass.
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

Time Complexity: O(1) for both get and put
Space Complexity: O(capacity)

We use a combination of hash map and doubly linked list to achieve O(1) operations. The hash map stores key-to-node mappings, and the doubly linked list maintains the order of recently used items.

Solution 1: Using list (Recommended - Python20 Optimized)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = 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)

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

How the code works:

  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.
  • Slow/fast pointers find middle or detect cycles in one pass.
Operation Time Space
get(key) O(1) O(1)
put(key, value) O(1) O(1)
Overall O(1) O(capacity)

Solution 2: Custom Doubly Linked List (Python20 Optimized)

class _Node:
    __slots__ = ("key", "val", "prev", "next")

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


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.mp: dict[int, _Node] = {}
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        p, n = node.prev, node.next
        p.next, n.prev = n, p

    def _add_to_front(self, node: _Node) -> None:
        n = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = n
        n.prev = node

    def get(self, key: int) -> int:
        if key not in self.mp:
            return -1
        node = self.mp[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.mp:
            node = self.mp[key]
            node.val = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.mp) >= self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.mp[lru.key]
        node = _Node(key, value)
        self.mp[key] = node
        self._add_to_front(node)

Solution 3: Most Optimized with Move Semantics

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = 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)

Key Optimizations (Python20)

  1. list::splice(): O(1) operation to move nodes without copying
  2. unordered_map::reserve(): Pre-allocates hash map to avoid rehashing
  3. explicit constructor: Prevents implicit conversions
  4. Structured bindings: Cleaner code with auto [key, value]
  5. emplace_front(): Constructs in-place, avoiding copies
  6. Move semantics: Efficient transfer of ownership

Data Structure Design

Hash Map:          Doubly Linked List:
key -> iterator    [head] <-> [1,1] <-> [2,2] <-> [tail]
                   (LRU)                (MRU)

Operation Flow

Get Operation:

  1. Look up key in hash map → O(1)
  2. If found, move node to front (most recently used) → O(1)
  3. Return value

Put Operation:

  1. Look up key in hash map → O(1)
  2. If exists: update value and move to front → O(1)
  3. If new:
    • Check capacity
    • If full: remove back node (LRU) → O(1)
    • Insert at front → O(1)

Example Walkthrough

capacity = 2

put(1, 1):  cache = {1: [1,1]}
            list: [head] <-> [1,1] <-> [tail]

put(2, 2):  cache = {1: [1,1], 2: [2,2]}
            list: [head] <-> [1,1] <-> [2,2] <-> [tail]

get(1):     Move [1,1] to front
            list: [head] <-> [2,2] <-> [1,1] <-> [tail]
            return 1

put(3, 3):  Evict [2,2] (LRU), add [3,3] at front
            cache = {1: [1,1], 3: [3,3]}
            list: [head] <-> [3,3] <-> [1,1] <-> [tail]

Why std::list is Preferred

  1. splice() is O(1): Moves nodes without copying
  2. Automatic memory management: No manual node deletion
  3. Less error-prone: No pointer management
  4. Better cache locality: Standard library optimizations
  5. Cleaner code: Less boilerplate

Common Mistakes

  1. Capacity = 1: Only one item can exist
  2. Get non-existent key: Returns -1
  3. Update existing key: Moves to front, doesn’t increase size

  4. Multiple puts: Evicts oldest when capacity exceeded

  5. Not moving to front on get: Must update access order
  6. Wrong eviction order: Remove from back (LRU), not front
  7. Memory leaks: Forgetting to delete nodes in custom implementation
  8. Not updating iterator: After list modification, iterators may be invalid
  9. Copying instead of moving: Use splice() or move semantics

Key Takeaways

  • Pattern: Iterative pointer walk (this problem)
  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.

References