AlgoViz
HomeStack

Monotonic Stack

Medium

Keep the stack sorted; each element enters and leaves once

Problem

Learn the monotonic stack pattern: keep the stack sorted so each element is pushed/popped once, solving next-greater/smaller style problems in O(n).

In simple words

A stack that only keeps useful candidates, throwing away ones that can never be the answer.

The idea

Before pushing an element, pop everything that breaks the ordering you are maintaining — and each pop is the moment you learn something about the popped element, namely that this new element is its next greater (or smaller) neighbour. Every element is pushed and popped at most once, so the whole sweep is O(n) despite the inner loop.

The trick

  • Increasing stack finds next-smaller; decreasing stack finds next-greater.
  • The answer for an element is discovered when it is popped, not when it is pushed.
  • Anything left on the stack at the end has no such neighbour.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
1
3
0
1
2

Step 1 of 2. Here's the example — next greater of [2,1,3] Values: 2, 1, 3.

1/2
Optimal
timeO(n)spaceO(n)
1for each element:2  pop while it breaks the order3  the new top is the answer; push element

Input

array
[2, 1, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
next greater of [2,1,3]
Output:
[3,3,-1]

Finished the walkthrough? Add it to your streak.