134. LRU Cache

An LRU cache needs two things: O(1) lookup by key, and O(1) reordering so the most recently used key sits at one end and the oldest sits at the other. Python's OrderedDict gives us both for free — move_to_end repositions a key in O(1), and popitem(last=False) evicts the oldest entry in O(1).

Why OrderedDict

OrderedDict is a hash map that also keeps insertion order. Crucially, it exposes:

• move_to_end(key, last=True) — bumps key to the most recently used end in O(1).
• popitem(last=False) — removes and returns the oldest entry in O(1).

Combine those with normal dict get/set and you have everything LRU needs.

Steps

For each operation:

• get(key):
  1. If key not in the dict, return -1.
  2. Otherwise move_to_end(key) (refreshes its recency) and return its value.
• put(key, value):
  1. If key already exists, move it to end (so the update counts as recent).
  2. Set self.od[key] = value (this also moves a brand-new key to the end automatically).
  3. If size now exceeds capacity, evict the oldest with popitem(last=False).

Walk-through

Capacity = 2.

Edge cases

• get on a missing key: return -1 without touching ordering.
• Updating an existing key: must move it to end and update the value. The implementation does both.
• Capacity 0: the eviction step would fire on every put, leaving the dict empty. (Most variants of this problem guarantee capacity ≥ 1.)

Complexity

• Time: O(1) amortized per get / put.
• Space: O(capacity) — the dict holds at most capacity entries.

import java.util.*;

class LRUCache {
    private int capacity;
    private LinkedHashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(capacity, 0.75f, true);
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        return map.get(key);
    }

    public void put(int key, int value) {
        map.put(key, value);
        if (map.size() > capacity) {
            int oldest = map.keySet().iterator().next();
            map.remove(oldest);
        }
    }
}

Build the data structure by hand to see why O(1) is achievable. We need (a) instant lookup by key — a hash map gives that. And (b) instant move-to-front + instant evict-from-back — a doubly linked list with sentinel head/tail nodes gives that. Wire them together: the hash map points at nodes, and each node knows its prev and next so it can detach itself in O(1).

The data structure

Two pieces working together:

1. Hash map self.map: key -> Node. Lets us locate a node by key in O(1).
2. Doubly linked list ordered most-recently-used → least-recently-used, with two sentinel nodes:
   • head (sentinel before the first real node)
   • tail (sentinel after the last real node) The node right after head is the most recently used. The node right before tail is the LRU candidate to evict.

Sentinels remove edge cases — there's always a node on either side of any real node, so detach/insert never has to special-case "first" or "last".

Two helper operations

• _remove(node): splice it out of the list. node.prev.next = node.next; node.next.prev = node.prev.
• _add_front(node): link it just after the head sentinel.

Steps

• get(key):
  1. If key not in self.map, return -1.
  2. Otherwise fetch node = self.map[key], _remove(node), _add_front(node). Return node.val.
• put(key, value):
  1. If key already exists, remove its node (we'll re-add at the front).
  2. Create a new Node(key, value), register it in self.map, and _add_front it.
  3. If len(self.map) > capacity, the LRU is at self.tail.prev. Remove it from the list and from the map.

Walk-through

Capacity = 2. Diagrams show the list left-to-right (head → … → tail).

put(1, 1):  head ↔ N1(1) ↔ tail              map = {1: N1}
put(2, 2):  head ↔ N2(2) ↔ N1(1) ↔ tail      map = {1: N1, 2: N2}
get(1):     # detach N1, re-insert at front
            head ↔ N1(1) ↔ N2(2) ↔ tail      map = {1: N1, 2: N2}    return 1
put(3, 3):  # add N3 at front, then evict — LRU is N2 (just before tail)
            head ↔ N3(3) ↔ N1(1) ↔ tail      map = {1: N1, 3: N3}
get(2):     # not in map                     return -1
put(4, 4):  # add N4 at front, evict N1
            head ↔ N4(4) ↔ N3(3) ↔ tail      map = {3: N3, 4: N4}
get(3):     head ↔ N3(3) ↔ N4(4) ↔ tail                              return 3

Why each operation is O(1)

• Hash map lookup / insertion / deletion: O(1) average.
• _remove: just rewires two pointers.
• _add_front: just rewires four pointers.
• Eviction targets tail.prev, which is reachable in O(1).

Edge cases

• Capacity 1: every put of a new key evicts the previous one; correctness still holds.
• Updating an existing key: the if key in self.map: _remove branch ensures we don't end up with two nodes for the same key.
• get on a missing key: does not touch the list — recency tracking only updates on hits.

Complexity

• Time: O(1) per get and put (hash ops + constant pointer manipulation).
• Space: O(capacity) — at most capacity nodes and map entries.