Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Monotonic Stack

Keep it sorted · bigger arrivals resolve the waiters
step 1 / 17
2
1
5
3
6
[0][1][2][3][4]
next greater
·
·
·
·
·
[0][1][2][3][4]
top ↓
(empty)
waiting (decreasing)
Concept
▸
1// next greater element, via a decreasing stack
2st = []                      // values waiting
3for each x in arr:
4    while st not empty and st.top < x:
5        pop — x is its next greater
6    push x
7// leftovers have no next greater
state
  • questionnext greater →

line 1A MONOTONIC stack is a stack we keep sorted on purpose. Demo question: for each element, what is the NEXT GREATER element to its right?