AlgoScope

Next Smaller Element

The nearest smaller value to the right.

Stack and queue algorithms, algorithm, intermediate
2 is smaller than the top value 6. 6 is popped and its answer is 2.602192431475i6 > 2
2 is smaller than the top value 6. 6 is popped and its answer is 2.602192431475i6 > 2

Monotonic Stack: Next smaller element

Decision, step 3 of 13

2 is smaller than 6, so 2 is the next smaller element of 6. Pop 6, which now has its answer.

How monotonic stack works

Cost

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

A variant of

Leads to

Topics that need this one first.

Taught by the same lesson

Monotonic Stack covers these too, in the same run.