Monotonic Stack Pattern
A monotonic stack maintains elements in increasing or decreasing order, popping as new elements violate the invariant. It answers 'next greater/smaller element' and spanning-range questions in O(n).
Typical complexity: O(n) time, O(n) space
When to use it
- You need the next/previous greater or smaller element.
- The problem involves spans, histograms, or temperatures.
- A brute force compares each element against later ones.
Practice problems
Read the approach or generate an interactive, step-by-step lesson:
Deep dive
Monotonic Stack Pattern: The Trick Behind Next Greater Element Problems
See how monotonic stacks help solve next greater, previous smaller, and histogram-style problems in linear time without brute force.
Master monotonic stack by doing
codebrew.ai turns each problem into an interactive lesson — trace the algorithm variable by variable until the pattern clicks.
Start a free lesson