When does a monotonic stack beat sorting?

Category: DSA Patterns

Answer

A monotonic stack maintains a sorted invariant — push while the stack’s top is greater than x (for next-smaller-to-right), pop and record when violated. The next greater element of each index is found in one pass. No sort needed.

Concrete examples from the fca project context

Example 1

Next Greater Element: stack stores indices; pop when current > stack top, current is the answer.

Example 2

Daily Temperatures: same as next greater; map index to wait days.

Example 3

Largest Rectangle in Histogram: stack stores index + height; max area on each pop.

Data flow / flow chart

iterate arr:
  while stack.top <= x: pop stack.top -> record answer
  push x

Takeaway

Next-greater / next-smaller / histogram: monotonic stack in O(N).