LRU Cache

Problem

Design a data structure that behaves like a fixed-size cache with a Least Recently Used (LRU) eviction policy. It is created with a positive capacity and supports two operations:

• get(key) — return the value stored for key, or -1 if key is not present. A successful get counts as using the key.
• put(key, value) — insert or overwrite the value for key. Inserting or overwriting also counts as using the key. If adding a new key would push the number of stored entries above capacity, first evict the key that was used least recently.

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

“Least recently used” means: among all keys currently in the cache, the one whose most recent get/put happened longest ago.

Examples

Example 1

LRUCache cache = new LRUCache(2)
put(1, 1)      // cache = {1=1}
put(2, 2)      // cache = {1=1, 2=2}
get(1)   -> 1  // 1 is now most-recently-used; order: 2 (old) ... 1 (new)
put(3, 3)      // capacity exceeded -> evict key 2; cache = {1=1, 3=3}
get(2)   -> -1 // 2 was evicted
put(4, 4)      // evict key 1; cache = {3=3, 4=4}
get(1)   -> -1
get(3)   -> 3
get(4)   -> 4

Example 2

LRUCache cache = new LRUCache(1)
put(1, 10)      // cache = {1=10}
put(2, 20)      // capacity 1 -> evict 1; cache = {2=20}
get(1)   -> -1
get(2)   -> 20

Overwriting an existing key never evicts, but it does refresh recency:

put(2, 99)      // cache = {2=99}, still size 1, no eviction
get(2)   -> 99

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4, 0 <= value <= 10^5
• Up to 2 * 10^5 calls total to get and put.
• Every get and put must be O(1) on average — this rules out scanning the cache to find the least-recently-used entry.

Think about it first

TL;DR

Hash map + doubly linked list (or an OrderedDict) — O(1) get/put, O(capacity) space.

Approach 1 — Naive: a list of (key, value) ordered by recency

Keep a Python list of [key, value] pairs with the front holding the most recent entry. get scans for the key and, on a hit, moves the pair to the front. put scans, updates or appends, and pops the last pair when over capacity.

from typing import List


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.items: List[List[int]] = []  # front = most recently used

    def get(self, key: int) -> int:
        for i, pair in enumerate(self.items):
            if pair[0] == key:
                self.items.pop(i)
                self.items.insert(0, pair)
                return pair[1]
        return -1

    def put(self, key: int, value: int) -> None:
        for i, pair in enumerate(self.items):
            if pair[0] == key:
                self.items.pop(i)
                self.items.insert(0, [key, value])
                return
        if len(self.items) >= self.capacity:
            self.items.pop()  # evict least recently used
        self.items.insert(0, [key, value])

Complexity: O(n) per operation — the linear scan plus pop(i)/insert(0, …) each shift elements. With up to 2·10^5 calls over a cache of 3000 entries this is too slow; the problem explicitly demands O(1).

Approach 2 — Hash map + doubly linked list

The two requirements, O(1) lookup and O(1) reordering by recency, each need a different structure, so combine both. A hash map gives O(1) key → node access. A doubly linked list keeps nodes in recency order; because each node knows its neighbours, unlinking it and splicing it to the front are O(1). Sentinel head and tail nodes remove the empty- and single-element edge cases.

The structure looks like this, with the map pointing directly at list nodes:

flowchart LR
    head["head (sentinel)"] <--> A["node: most recent"] <--> B["node"] <--> C["node: least recent"] <--> tail["tail (sentinel)"]
    map["hash map: key to node"] -.-> A
    map -.-> B
    map -.-> C

class Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev: "Node | None" = None
        self.next: "Node | None" = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: dict[int, Node] = {}
        self.head = Node()  # sentinel: most-recently-used side
        self.tail = Node()  # sentinel: least-recently-used side
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add_front(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_front(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Walkthrough on Example 1 (capacity = 2):

1. put(1,1) → list: head ⇄ 1 ⇄ tail, cache {1}.
2. put(2,2) → head ⇄ 2 ⇄ 1 ⇄ tail, cache {1,2}.
3. get(1) → hit; unlink 1, splice to front: head ⇄ 1 ⇄ 2 ⇄ tail. Now 2 is the LRU. Returns 1.
4. put(3,3) → new node to front: head ⇄ 3 ⇄ 1 ⇄ 2 ⇄ tail, size 3 > 2. Evict tail.prev = node 2, del cache[2]. List: head ⇄ 3 ⇄ 1 ⇄ tail.
5. get(2) → not in cache → -1.
6. put(4,4) → front insert, over capacity, evict LRU = node 1. List: head ⇄ 4 ⇄ 3 ⇄ tail.
7. get(1) → -1, get(3) → 3, get(4) → 4.

Complexity: O(1) per get/put — hash lookup plus a constant number of pointer swaps. O(capacity) space for the nodes and map.

Approach 3 — collections.OrderedDict

An OrderedDict is already a hash map backed by a doubly linked list, and it exposes the two O(1) moves this problem needs: move_to_end(key) to mark recency and popitem(last=False) to evict from the front. This reduces Approach 2 to a few lines. A plain dict also preserves insertion order in modern Python and works with next(iter(cache)) to find the oldest key.

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)  # mark as most recently used
        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)  # evict least recently used

Walkthrough on Example 2 (capacity = 1): put(1,10) → {1:10}. put(2,20) → insert {1:10, 2:20}, size 2 > 1, popitem(last=False) drops the oldest 1 → {2:20}. get(1) → -1. get(2) moves 2 to end (no-op, it is the only key) → 20.

Complexity: O(1) per operation, O(capacity) space — same as Approach 2, with the linked-list bookkeeping delegated to the standard library.

Common pitfalls

• Forgetting that get counts as a use: a hit must move the key to the most-recently-used end, or the eviction order goes stale.
• Overwrite vs. insert: put on an existing key must refresh recency but must not evict — the size is unchanged. Deleting-then-reinserting (Approach 2) handles both uniformly.
• Order of insert and evict: insert the new node first, then check len > capacity. Evicting before insertion can wrongly drop the entry you just added when capacity is 1.
• Losing the key on eviction: when you unlink the LRU node you must also del it from the hash map, otherwise the map grows unbounded and get returns a value whose node is gone.
• Manual pointer bugs: without sentinel head/tail nodes, inserting into or removing from an empty list needs special cases that are easy to get wrong.

Pattern takeaway

When one operation needs O(1) lookup and another needs O(1) ordered removal, pair a hash map with a doubly linked list: the map finds the node, the list reorders it. Sentinel nodes eliminate the edge cases. Before hand-rolling the list, note that Python’s OrderedDict already bundles this map-plus-linked-list structure.