LRU Cache (LeetCode 146)

The problem

Design a class LRUCache(cap) that stores up to cap key-value pairs and supports:

• get(key): return the value if the key is present, otherwise -1. A successful get counts as using the key.
• put(key, val): insert or update the key, which also counts as using it. If this makes the cache hold more than cap keys, evict the least recently used one.

Both operations must run in O(1) average time.

cap = 2
put(1, 1)   put(2, 2)   get(1) -> 1
put(3, 3)   (evicts key 2)
get(2) -> -1
put(4, 4)   (evicts key 1)
get(1) -> -1   get(3) -> 3   get(4) -> 4

After get(1), key 2 is the stalest, so put(3, 3) evicts it. Then key 1 is the stalest when put(4, 4) arrives.

How to think about it

Start with brute force. Store pairs in a list ordered by recency. A lookup scans the list (O(n)), and moving a used key to the front shifts elements (O(n)). Or store a “last used” timestamp in a dictionary: lookups are O(1), but finding the oldest key to evict is an O(n) scan.

Two needs, two structures. You need fast lookup by key (a hash map) and fast “who is oldest?” plus fast “move this one to newest” (an ordered list where any element can be moved in O(1)). Neither alone does both.

The key insight: link them. Keep the items in a doubly linked list ordered by recency, and a hash map from key to node. The map finds a node in O(1). Because the list is doubly linked, that node can be unlinked and re-inserted at the “recent” end in O(1). The least recently used item is always at the other end, so eviction is O(1) too.

Python already has this structure. OrderedDict is a hash map backed by a doubly linked list. move_to_end(key) marks a key as most recent, and popitem(last=False) removes the oldest. Use it when allowed; know the hand-built version for when the interviewer says “without OrderedDict”.

Which pattern is this? Hash map plus an ordered structure (design a data structure). The tell is “O(1) lookup and O(1) ordering by recency”.

Approach

1. Keep an OrderedDict d, oldest key first, newest key last.
2. get: if the key is missing, return -1. Otherwise move it to the end (most recent) and return its value.
3. put: if the key exists, move it to the end first. Set its value (new keys are added at the end).
4. If d now holds more than cap keys, pop from the front: that’s the least recently used.

Solution

from collections import OrderedDict

class LRUCache:
    def __init__(self, cap):
        self.cap = cap; self.d = OrderedDict()          # oldest first, newest last
    def get(self, key):
        if key not in self.d: return -1
        self.d.move_to_end(key); return self.d[key]     # mark as most recent
    def put(self, key, val):
        if key in self.d: self.d.move_to_end(key)
        self.d[key] = val
        if len(self.d) > self.cap: self.d.popitem(last=False)   # evict the oldest
# cap=2: put(1,1) put(2,2) get(1)->1 put(3,3) get(2)->-1 ...

Alternative: hash map + doubly linked list

class Node:
    def __init__(self, k=0, v=0):
        self.k = k; self.v = v; self.prev = None; self.next = None

class LRUCache:
    def __init__(self, cap):
        self.cap = cap; self.m = {}                       # key -> node
        self.head = Node(); self.tail = Node()            # sentinels
        self.head.next = self.tail; self.tail.prev = self.head
    def _remove(self, n):
        n.prev.next = n.next; n.next.prev = n.prev
    def _add(self, n):                                    # insert right after head (most recent)
        n.prev = self.head; n.next = self.head.next
        self.head.next.prev = n; self.head.next = n
    def get(self, key):
        if key in self.m:
            n = self.m[key]; self._remove(n); self._add(n); return n.v
        return -1
    def put(self, key, val):
        if key in self.m: self._remove(self.m[key])
        n = Node(key, val); self.m[key] = n; self._add(n)
        if len(self.m) > self.cap:
            lru = self.tail.prev; self._remove(lru); del self.m[lru.k]   # evict next to tail
# cap=2: put(1,1) put(2,2) get(1)->1 put(3,3) get(2)->-1 put(4,4) get(1)->-1 get(3)->3 get(4)->4

This is what OrderedDict does internally, written out by hand. The dummy head and tail sentinels mean _remove and _add never need None checks. Each node stores its key so that eviction can delete the right map entry. Expect to write this version when an interviewer rules out library help (Lesson 27 covers it as a design problem).

Dry run

The OrderedDict version with cap = 2. The state lists keys from oldest to newest:

Both versions return the same sequence for the five gets: 1, -1, -1, 3, 4.

Complexity

• Time: O(1) average for get and put. Every step is a hash lookup or a constant number of pointer changes.
• Space: O(cap). At most cap + 1 entries exist at once, and only briefly before eviction.

Edge cases and pitfalls

• Updating an existing key must also refresh its recency. With cap = 2, put(1,1) put(2,2) put(1,10) put(3,3) evicts key 2, and get(1) returns 10.
• Capacity 1: every new key evicts the previous one; both versions handle it.
• A failed get doesn’t change order. Only hits count as “use”.
• Forgetting to store the key in the node leaves you unable to delete the evicted entry from the map.
• Singly linked list: removing a node from the middle needs its predecessor, which is O(n) to find. That’s why the list must be doubly linked.

Related problems

• LFU Cache (LeetCode 460): evict by least frequent, with recency to break ties.
• Design HashMap (LeetCode 706): build the hash map itself.
• Copy List with Random Pointer (LeetCode 138): another problem where a map from key to node does the heavy lifting.