Monotonic Stack
A stack maintained in sorted order to find next greater/smaller elements.
What is this pattern?
A monotonic stack keeps elements in strictly increasing or decreasing order. When a new element violates the order, you pop and process elements from the stack — each pop answers the "next greater/smaller element" query for that popped element in O(1) amortized.
When to use it
- Finding the next greater or smaller element for each position
- Calculating spans, areas, or distances based on surrounding elements
- Keywords: "next greater", "daily temperatures", "histogram", "trapping water"
- Processing elements where future elements affect past calculations
Key Insight
Elements are pushed and popped at most once → O(n) total. For "next greater to the right", iterate left-to-right with a decreasing stack. For "previous smaller", iterate right-to-left or use an increasing stack.
Pro Content
The Java template and practice problems for this pattern are part of the Pro plan. Upgrade to unlock all patterns, 500+ problems, and Aria code reviews.
From ₹3,999 for a year · one-time, no auto-renewal