146. LRU Cache

Problem¶

Implement LRUCache(capacity) with average \(O(1)\) get and put; every successful access marks a key as most recently used, and inserting beyond capacity evicts the least recently used key.

capacity = 2
put(1, 1) -> [1]
put(2, 2) -> [1, 2]
get(1)    -> 1;  order [2, 1]
put(3, 3) -> evict 2; order [1, 3]
get(2)    -> -1

Key trick¶

Combine a hash map for \(O(1)\) lookup with a doubly linked list that stores keys from least to most recently used, allowing \(O(1)\) removal and movement.

Trap¶

Updating or successfully reading an existing key must move it to the most-recent position.
Assigning an existing key in a regular Python dictionary does not change its insertion order.
Timestamps can contain gaps, so incrementing the oldest timestamp does not necessarily locate an existing entry.
Eviction must remove the key from both the map and the linked list.

Why is it interesting?¶

It tests how two data structures can compensate for each other's limitations to satisfy several \(O(1)\) operations simultaneously.

Python solution¶

The required interface is a standalone LRUCache class rather than a method of Solution.

from collections import OrderedDict

class LRUCache:
    class Node:
        def __init__(self, key=0, val=0):
            self.key = key
            self.val = val
            self.prev = None
            self.next = None

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}

        # Sentinels avoid special cases when adding or removing nodes.
        self.lru = self.Node()
        self.mru = self.Node()
        self.lru.next = self.mru
        self.mru.prev = self.lru

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

    def _mark_recent(self, node) -> None:
        # Insert immediately before the MRU sentinel.
        prev = self.mru.prev
        prev.next = node
        node.prev = prev
        node.next = self.mru
        self.mru.prev = node

    def get(self, key: int) -> int:
        if key not in self.nodes:
            return -1

        node = self.nodes[key]
        self._remove(node)
        self._mark_recent(node)
        return node.val

    def put(self, key: int, val: int) -> None:
        if key in self.nodes:
            node = self.nodes[key]
            node.val = val
            self._remove(node)
            self._mark_recent(node)
            return

        node = self.Node(key, val)
        self.nodes[key] = node
        self._mark_recent(node)

        if len(self.nodes) > self.capacity:
            # The first real node is the least recently used.
            evicted = self.lru.next
            self._remove(evicted)
            del self.nodes[evicted.key]


class LRUCache:
    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

        # Move a successful access to the most-recent end.
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, val: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)

        self.cache[key] = val

        if len(self.cache) > self.capacity:
            # The first entry is the least recently used.
            self.cache.popitem(last=False)

Each operation takes average \(O(1)\) time, and the cache uses \(O(\text{capacity})\) space.

Comment on my solution¶

The timestamp idea fails because access times are not contiguous after updates. Incrementing lowest_access_time by one can point to a timestamp already deleted from access_time_to_key.

For the failing test, both old timestamps are removed by later accesses, but lowest_access_time advances to only the first missing timestamp. The next eviction therefore raises KeyError.

Searching forward for the next valid timestamp would repair correctness but loses the clean per-operation \(O(1)\) guarantee; a doubly linked list explicitly tracks the next least-recent entry.

# WRONG
# Runtime Error: 13/25 testcases passed
# ["LRUCache","put","put","get","get","put","get","get","get"]
# [[2],[2,1],[3,2],[3],[2],[4,3],[2],[3],[4]]
# KeyError: 1 | evict_key = self.access_time_to_key[self.lowest_access_time]
class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {} # key -> [value, last_access_time]
        self.access_time_to_key = {}
        self.lowest_access_time = -1
        self.last_access_time = -1

    def _update(self, key):
        key_last_access_time = self.cache[key][1]
        del self.access_time_to_key[key_last_access_time]

        if self.lowest_access_time == key_last_access_time:
            self.lowest_access_time += 1

        self.last_access_time += 1

        self.access_time_to_key[self.last_access_time] = key
        self.cache[key][1] = self.last_access_time

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        self._update(key)
        return self.cache[key][0]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._update(key)
            self.cache[key][0] = value
            return

        if len(self.cache) == self.capacity:
            evict_key = self.access_time_to_key[self.lowest_access_time]
            del self.access_time_to_key[self.lowest_access_time]
            del self.cache[evict_key]
            self.lowest_access_time += 1

        self.last_access_time += 1
        self.cache[key] = [value, self.last_access_time]
        self.access_time_to_key[self.last_access_time] = key

        if self.lowest_access_time == -1:
            self.lowest_access_time = 0