Algorithms / Monotonic Stack Next Greater
Least You Need to Know: Monotonic Stacks and Next-Greater Patterns
A monotonic stack keeps elements in sorted stack order so that a new value can resolve many waiting positions at once. This turns repeated scanning into a single left-to-right pass for next-greater and waiting-time style problems.
Least you need to know
- For next-greater problems, the stack usually stores indices whose answer has not been found yet.
- A new larger value can pop smaller waiting values and become their answer.
- The chosen monotone direction depends on whether you need next greater, next smaller, previous greater, or previous smaller.
- Indices are often more useful than raw values because you may need distances or window membership.
- Each index is pushed once and popped once, giving linear-time behavior.
Key notation
- stack — LIFO structure holding unresolved candidates
- monotone decreasing — stored values decrease from bottom to top
- next greater — first later value strictly larger than the current one
Worked example
- Scan array values from left to right.
- Keep a decreasing stack of indices whose next greater value has not appeared yet.
- When a larger value arrives, pop all smaller indices and record the new value or new index as their answer.
- Then push the current index.
Common mistakes
- Students often store values when later they need distances between indices.
- Students often forget that equal values require a deliberate tie rule.
- Students often think monotonic stacks sort the entire array instead of solving pending boundary questions.
How to recognize it
- The prompt asks for next greater, warmer day, first taller bar, or nearest later blocker.
- Each position waits for the first later element meeting a comparison.
- A brute-force nested scan would repeatedly revisit the same comparisons.
Next recommended lesson
Continue through this topic with Least You Need to Know: Offline Sorting, Event Sweeps, and Ordered Processing.
Least You Need to Know: Offline Sorting, Event Sweeps, and Ordered ProcessingRelated lessons
Keep going with nearby lessons in the same topic.