IntermediateStack
Monotonic stack: the next greater element
Keep a stack of indices still waiting for a bigger value. Each new value pops everyone it beats; that's their answer.
The idea
For “next warmer day” or “next greater element”, a brute force looks right from every index: O(n²). Instead, walk once and keep a stack of indices that haven't found their answer yet. Their values decrease from bottom to top.
When a new value is bigger than the top, the top's answer is the current index: pop it and repeat. Every index is pushed and popped at most once, so it's O(n).
Worked example
Daily Temperatures: [73, 74, 75, 71, 69, 72, 76]
- 73 waits. 74 > 73 → day 0 waited 1. 75 > 74 → day 1 waited 1.
- 71, 69 wait under 75. 72 > 69 → day 4 waited 1; 72 > 71 → day 3 waited 2.
- 76 beats 72 and 75 → day 5 waited 1, day 2 waited 4.
In code (Python)
def daily_temperatures(temps):
answer = [0] * len(temps)
stack = [] # indices, temps decreasing
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answerO(n) time, O(n) space.
How to spot it
- “next greater / smaller”, “days until”, spans, largest rectangle in a histogram.
Common mistakes
- Pushing values instead of indices, so you can't compute distances.
- Using <= vs < wrongly for equal values.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →