Monotonic Stack: when to spot it, explain it, and practice it
Monotonic stack is how you turn repeated nearest-boundary searches into one pass. When every element wants to know who defeats it first on the left or right, the stack is doing structural compression for you.
Pattern coverage
25+
Best first move
Choose increasing or decreasing stack based on what should remain unresolved.
Common failure point
Using values instead of indices and losing distance information.
When this pattern should come to mind
Checklist before you code
The solving flow that works well in interviews
Decide what unresolved property the stack maintains.
Push indices while the monotonic invariant holds.
Pop while the current value resolves earlier items.
Record answers at pop time because that is when the boundary becomes known.
Process leftovers for default answers or widths.
Common variants
Next greater / smaller
The most direct monotonic-stack pattern.
Boundary width
Find the left and right boundary for each bar or element.
Circular scan
Iterate twice when the array wraps around logically.
Template preview
stack = []
for i, value in enumerate(nums):
while stack and nums[stack[-1]] < value:
prev_index = stack.pop()
# value is the next greater for prev_index
stack.append(i)
Classic problems with useful framing
#739
Daily Temperatures
The cleanest introduction to unresolved-next-greater logic.
For each day, find how many days until a warmer temperature.
#84
Largest Rectangle in Histogram
Shows how boundaries turn into area calculations.
Find the largest rectangle area in a histogram.
#503
Next Greater Element II
A good circular-array extension.
Find the next greater element in a circular array.
A more useful problem ladder for practice
This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.
Foundation
#20 Valid Parentheses
Check whether a bracket string is valid.
Every closing bracket must match the most recent unmatched opening bracket, not an arbitrary earlier one.
Foundation
#155 Min Stack
Design a stack that supports retrieving the minimum in O(1).
Each push must also record what the minimum becomes at that depth.
Variant depth
#503 Next Greater Element II
Find the next greater element in a circular array.
The second pass exists only to resolve elements left unanswered from the first pass.
Variant depth
#739 Daily Temperatures
For each day, find how many days until a warmer temperature.
Store unresolved indices in a decreasing stack; the current warmer day resolves all smaller temperatures behind it.
Pressure test
#84 Largest Rectangle in Histogram
Find the largest rectangle area in a histogram.
When a bar is popped, the current index is its first smaller bar on the right, and the new stack top becomes its first smaller bar on the left.
High-frequency mistakes
Using values instead of indices and losing distance information.
Choosing the wrong comparison operator for equal elements.
Forgetting the second pass in circular-array questions.
Missing sentinel handling in histogram problems.
Recommended practice path
Start with daily temperatures and next greater element.
Then solve histogram rectangle problems.
Add circular variants next.
Finish with harder contribution-counting problems that use boundaries indirectly.