Monotonic Stack

Next Greater & Stack Invariants

1:00

How a stack kept in sorted order solves "nearest greater / smaller" queries for every element in a single O(n) pass.

By the end, you can

Explain what invariant a monotonic stack maintains and why it enables linear-time nearest-neighbor queries.
Trace the decreasing stack on a small array and produce the complete next-greater result array.
Identify which stack flavor (increasing vs. decreasing) solves each of the four nearest-neighbor variants.
Argue why the algorithm is O(n) amortized despite the nested while loop.
Explain why indices are stored on the stack rather than raw values.
Read the "previous greater" answer off the same left-to-right scan without a second pass.
Apply the monotonic stack pattern to Daily Temperatures and Largest Rectangle in a Histogram.
Recognize "nearest greater/smaller," "span," and "boundary" problem phrasings as signals to use a monotonic stack.

Up next in Coding Interview Patterns