AlgoScope

Previous Greater Element

The nearest larger value to the left, via a monotonic stack.

Stack and queue algorithms, algorithm, intermediate
4 is greater than 3. The answer for 3 is 4, and 3 is pushed.40311273548526itop4 > 3
4 is greater than 3. The answer for 3 is 4, and 3 is pushed.40311273548526itop4 > 3

Monotonic Stack: Previous greater element

Decision, step 3 of 14

4 is greater than 3, so 4 is the previous greater element of 3. Push 3.

How monotonic stack works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

A variant of

Taught by the same lesson

Monotonic Stack covers these too, in the same run.