AlgoScope

Next Greater Element

Scan with a monotonic stack. Each pop resolves an element's answer.

Stack and queue algorithms, algorithm, intermediate
8 is greater than the top value 5. 5 is popped and its answer is 8.40311273548526topi5 < 8
8 is greater than the top value 5. 5 is popped and its answer is 8.40311273548526topi5 < 8

Monotonic Stack: Next greater element

Decision, step 10 of 15

8 is greater than 5, so 8 is the next greater element of 5. Pop 5, which now has its answer.

Cost

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

Before this

Variants

  • Previous Greater ElementScan left to right
  • Next Smaller ElementSame with the inequality flipped.
  • Previous Smaller ElementFlip both direction and inequality.

Leads to

Topics that need this one first.

Taught by the same lesson

Monotonic Stack covers these too, in the same run.