Explain how a monotonic stack solves the 'next greater element' problem in linear time, and how you recognize at review time that a quadratic nested-loop solution should actually be a monotonic stack.

technical-conceptual · Senior level · software-engineering

What the interviewer is really asking

Assesses whether the candidate can give the amortized linear-time argument for a monotonic stack, explain the invariant that makes it correct, and pattern-match the problem shape — turning an O(n^2) scan into O(n) — rather than reciting a template.

What to say

• Explain the mechanism and invariant: you keep a stack of indices whose values are monotonic (e.g. decreasing); when the current element is greater, you pop everything smaller and each popped element has just found its next greater element — the stack always holds elements still waiting for an answer.
• Give the amortized argument: despite the inner while-loop, every index is pushed once and popped at most once across the whole scan, so total work is O(2n) = O(n), not O(n^2) — the nested loop is a red herring.
• State the recognition signal: at review I flag any double loop that, for each element, scans forward/backward for the nearest element satisfying a comparison (next/previous greater or smaller, days-until-warmer, stock span, largest rectangle) — that 'nearest element by a monotonic comparison' shape is the monotonic-stack tell.

What to avoid

• Calling it O(n^2) because of the inner while-loop, missing the amortized argument that each index is pushed and popped at most once.
• Presenting the template without stating the invariant (the stack holds elements still awaiting their answer) so you can't explain WHY it's correct.
• Failing to recognize the pattern from the problem shape and instead defending the quadratic nested scan as 'clear enough.'

Example answers

Strong: I keep a stack of indices with monotonically decreasing values. As I scan, whenever the current value exceeds the value at the stack top, I pop — and each popped index has just found its next greater element, which is the current one. The stack invariant is that it only holds elements still waiting for a greater neighbor. The inner while-loop tempts people to say O(n^2), but each index is pushed exactly once and popped at most once, so the total is O(n) amortized. In review, the tell is a nested loop that for each element searches forward or backward for the nearest larger or smaller value — next-greater, stock span, daily temperatures, largest rectangle in a histogram. That shape means I should coach it toward a monotonic stack.

Weak: For each element I scan the rest of the array to find the next bigger one. To speed it up you can use a stack — push and pop values so you don't rescan, and that makes it faster than the double loop.