Algorithms / Monotonic Stack Boundaries
Least You Need to Know: Monotonic Stacks for Range Boundaries and Histogram Areas
Monotonic stacks do more than next-greater queries: they also expose the nearest smaller or larger boundary on each side. That boundary view powers classic problems like largest rectangle in a histogram and contribution counting.
Least you need to know
- Previous-smaller and next-smaller boundaries define the maximal span where a bar remains the minimum height.
- Histogram area is height times width between the first smaller bar on the left and the first smaller bar on the right.
- Boundary problems often need a consistent tie rule when equal values appear.
- A shorter arriving bar can finalize the area or range for taller bars on the stack.
- The stack stores candidates whose boundary has not yet been closed.
Key notation
- prev smaller — nearest earlier index with a strictly smaller value
- next smaller — nearest later index with a strictly smaller value
- width — count of indices between the two blocking boundaries
Worked example
- In a histogram, keep bars in increasing-height stack order.
- When a shorter bar arrives, pop taller bars because their right boundary is now known.
- The new stack top gives the left boundary for each popped bar.
- Compute area immediately while that bar's maximal span is fully known.
Common mistakes
- Students often compute width incorrectly by forgetting to exclude blocking boundaries.
- Students often use inconsistent tie rules with equal heights and double-count spans.
- Students often miss that a sentinel bar can flush remaining stack items cleanly at the end.
How to recognize it
- You need the nearest smaller or larger boundary on both sides.
- The quantity for one position becomes known exactly when a blocking value arrives.
- Histogram, span, and subarray-minimum contribution problems often share this structure.
Next recommended lesson
Continue through this topic with Least You Need to Know: Monotonic Stacks and Next-Greater Patterns.
Least You Need to Know: Monotonic Stacks and Next-Greater PatternsRelated lessons
Keep going with nearby lessons in the same topic.