Monotonic Structures
Discard dominated candidates while preserving monotonic order.
The idea
Monotonic structures turn repeated local comparisons into linear-time scans by discarding dominated candidates as soon as they become provably useless. The order invariant does the heavy lifting; stack or deque is only the storage detail.
Use a monotonic stack when each value waits for a future boundary (next greater, span, area). Use a monotonic deque when a moving window needs a live optimum and stale candidates must expire from the front.
Think of keeping only contenders in a tournament bracket: weaker contenders are eliminated immediately, and outdated contenders leave as their eligibility window ends.
When to reach for it
- You need nearest greater/smaller relationships without nested rescans.
- You need a per-window maximum or minimum while the window slides.
- Candidates can be proven useless by a stronger newer candidate.
Language-independent template
for each index i:
remove expired candidates (queue modes)
while structure has dominated candidates:
remove dominated candidate
insert i
read answer from top/front when condition is metComplexity — time O(n), space O(n) (Each index is inserted and removed at most once.).
Common mistakes
- Using values instead of indices when distance or expiration matters.
- Choosing the wrong comparison direction for increasing vs decreasing invariants.
- Reading window answers before removing expired front indices.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Find the first greater value to the right of each queried value.
For each day, count how long until a warmer temperature.
Find the largest rectangle formed by contiguous bars.
Return the maximum value in every window of size k.
Find the shortest subarray whose sum reaches K, even with negatives.