Monotonic Stack

Keep a stack whose elements stay sorted, popping anything that breaks the order — the trick behind "next greater element" and histogram problems in O(n).

Key ideas

  • —Maintain a stack that is always increasing or always decreasing.
  • —When a new element breaks the order, popping resolves answers for the popped items.
  • —Each element is pushed and popped at most once, so the total cost is O(n).

Why amortized O(n)

A monotonic stack processes each element by popping everything that violates the desired order before pushing the new element. Although a single step can pop many items, every element enters and leaves the stack exactly once across the whole scan, so the total work is linear despite the inner loop.

Resolving "next greater" and spans

The pop is where answers are produced: when element x pops element y, x is precisely y's next greater (or next smaller) value. Largest Rectangle in a Histogram uses this to find, for each bar, how far it can extend before a shorter bar blocks it, and Basic Calculator uses a stack to defer operations until precedence resolves.

Practice this

Sources

← All lessonsNext: Prefix Sum →