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-iterator mappings, and the doubly linked list maintains the order of recently used items.

Solution: Using std::list with splice

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
            return
        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) |

Thread-Safe LRU Cache

Thread-safe version using mutex for concurrent access.

import threading
from collections import OrderedDict


class ThreadSafeLRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()
        self._lock = threading.Lock()

    def get(self, key: int) -> int:
        with self._lock:
            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:
        with self._lock:
            if key in self.cache:
                self.cache.move_to_end(key)
                self.cache[key] = value
                return
            self.cache[key] = value
            if len(self.cache) > self.capacity:
                self.cache.popitem(last=False)

    def size(self) -> int:
        with self._lock:
            return len(self.cache)

Thread-Safe Implementation Details

  1. shared_mutex: Allows multiple concurrent reads when no writes are happening
  2. unique_lock<shared_mutex>: Exclusive lock for both get() and put() since they modify the list
  3. shared_lock<shared_mutex>: Shared lock for read-only operations like size()
  4. Note: The thread-safe put() calls get() which requires careful lock management - both methods use exclusive locks

Solution Explanation

Data Structure Design

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

Operation Flow

Get Operation:

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

Put Operation:

  1. Check if key exists via get() → O(1)
  2. If exists: update value (already moved to end by get()) → O(1)
  3. If new:
    • Check capacity
    • If full: remove front node (LRU) → O(1)
    • Insert at end → O(1)

Example Walkthrough

capacity = 2

put(1, 1):  cache = {1: (1, it1)}
            list: [1]

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

get(1):     Move 1 to end using splice
            list: [2] <-> [1]
            return 1

put(3, 3):  get(3) returns -1, capacity full
            Remove front (key 2), insert 3 at end
            cache = {1: (1, it1), 3: (3, it3)}
            list: [1] <-> [3]

Complexity

| Operation | Time | Space | |———–|——|——-| | get(key) | O(1) | O(1) | | put(key, value) | O(1) | O(1) | | Overall | O(1) | O(capacity) |

Why This Approach Works

  1. Hash map: Provides O(1) lookup by key
  2. Doubly linked list: Maintains insertion order and allows O(1) removal/insertion
  3. Iterator storage: Hash map stores iterators to list nodes for O(1) access
  4. splice() optimization: Moves nodes without copying, maintaining O(1) complexity

Common Mistakes

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

  4. Multiple puts: Evicts oldest when capacity exceeded

  5. Not moving to end on get: Must update access order
  6. Wrong eviction order: Remove from front (LRU), not back
  7. Invalid iterator after modification: Use splice() which preserves iterators
  8. Not handling existing key in put: Must check and update, not just insert

Key Takeaways

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

References