When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Next greater or smaller
- Span until obstruction
When another approach fits better
- You need arbitrary range minima with updates
- The required candidate order is FIFO by time rather than nearest boundary under value order
How it works#
For every position, scan left or right until the first qualifying boundary, costing O(n²) in a monotone input.
Decide greater/smaller and strict/non-strict behavior.
Store indices when distance or original position matters.
Pop while the current value resolves the top, then push the current unresolved index.
InvariantStack indices are unresolved and their values remain monotonic; popping resolves or discards each dominated index permanently.
Example and template#
Daily Temperatures
Introduces unresolved candidates without making monotonic structures a prerequisite.
Open the full problem brief- Before 75
stack values [73, 74]Both indices wait for a warmer value.
- Read 75
pop 74, pop 73, push 75The current value resolves both; each leaves permanently.
stack = empty indices
for i in 0..n-1:
while stack not empty and input[i] resolves input[stack.top]:
j = pop
answer[j] = relation(i, j)
push i- Time
- O(n) amortized
- Space
- O(n)
- Assumptions
- Each index is pushed once and popped at most once; equality handling matches the problem.
Pitfalls#
Common wrong approaches
Distances and duplicate positions require original indices.
Using < versus ≤ changes whether equal values resolve or coexist.
Edge cases
- Equal adjacent values
- Strictly increasing/decreasing input
- Unresolved suffix
- Circular sequence
Interview narration
- “The stack contains only unresolved indices.”
- “Any smaller top is permanently resolved by the current value.”
- “Each index enters and leaves once, which makes the nested while loop linear overall.”
Practice#
Daily Temperatures
Introduces unresolved candidates without making monotonic structures a prerequisite.
Practice this problemFor every bar, find the first later bar that is strictly shorter.
Reveal the pattern decision
Use a monotonic increasing stack of unresolved indices and resolve on a smaller current value.
Transfer problem
Compute the largest rectangle in a histogram.
Checkpoint: Treat a shorter bar as the right boundary for popped heights and derive each left boundary from the new stack top.
Follow-up variations
- Adapt to a circular array
- Use a monotonic deque for sliding-window extrema
Error-log prompts
- Was the monotonic direction correct?
- What happened on equal values?