The question this module answers: which part of the past do you still need? Many problems walk through a sequence and, at each step, ask something about what came before: the bracket that is still open, the most recent higher value, the oldest request still waiting, the largest value in the last k steps. Keeping all the past and rescanning it is O(n) per step. Keeping exactly the part that can still matter, in the right order, makes each step O(1) on average.
ML context. These structures sit under a lot of ML infrastructure:
- Queues: request queues in model servers, data-loader prefetch buffers, breadth-first traversal of graphs.
- Stacks: parsing and validating structured model output (JSON, tool calls), depth-first traversal, undo history.
- Bounded deques: the last k losses for a rolling mean, a replay buffer of recent experience.
- Monotonic structures: the rolling maximum of GPU memory or latency over a window (lesson 6.10), "how long until this metric was beaten".
1. The problem: rescanning the past
Task: for each position i, return the index of the previous greater element: the closest j < i with
a[j] > a[i], or −1 if there is none.
The obvious approach walks backwards from each position: