Advanced Open Free

LRU Cache

Design a data structure for a Least Recently Used (LRU) cache that supports the following operations, both in O(1) average time:

get(key): return the value associated with key if it exists in the cache, otherwise return -1. Accessing a key counts as using it, so it becomes the most recently used entry.
put(key, value): insert or update the value for key. If inserting a new key would exceed the cache's fixed capacity, evict the least recently used entry first. Inserting or updating a key also counts as using it.

Example

cache = LRUCache(capacity=2)
cache.put(1, 1)          # cache: {1=1}
cache.put(2, 2)          # cache: {1=1, 2=2}
cache.get(1)              # returns 1, cache order (MRU->LRU): 1, 2
cache.put(3, 3)          # evicts key 2 (LRU), cache: {1=1, 3=3}
cache.get(2)              # returns -1 (not found)
cache.put(4, 4)          # evicts key 1 (LRU), cache: {3=3, 4=4}
cache.get(1)              # returns -1 (not found)
cache.get(3)              # returns 3
cache.get(4)              # returns 4

Constraints

1 <= capacity <= 3000.
0 <= key, value <= 10^4.
At most 2 * 10^5 calls to get and put combined.
Both get and put must run in O(1) average time.

Solution

A hash map alone gives O(1) get/put by key, but it doesn't track recency order, so eviction would require an O(n) scan. An array or Python list also fails, since removing/reinserting an item to mark it "most recently used" is O(n). The fix is to combine a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering and O(1) removal of the least-recently-used node) — the two-pointer prev/next links let you splice any node out of the middle of the list without walking it.

Maintain the doubly linked list ordered from most-recently-used (right after a head sentinel) to least-recently-used (right before a tail sentinel). The hash map stores key -> node so any node can be found and unlinked in O(1), then relinked next to head. On overflow, evict the node just before tail.

class DLLNode:
    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.map = {}  # key -> DLLNode
        # Sentinels simplify edge cases at the ends of the list.
        self.head = DLLNode()
        self.tail = DLLNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: DLLNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

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

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)  # mark as most recently used
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = DLLNode(key, value)
        self.map[key] = node
        self._add_to_front(node)

        if len(self.map) > self.capacity:
            lru = self.tail.prev  # least recently used
            self._remove(lru)
            del self.map[lru.key]

Complexity: O(1) average time for both get and put — hash map lookup is O(1), and doubly linked list splicing is O(1) since we hold direct references to prev/next and never scan. O(n) extra space for the hash map and list nodes, where n is the capacity.

Share this question

Share on X Share on LinkedIn

← Back to Linked Lists practice