Monotonic stack
Keep a stack whose values only decrease (or increase) so each element finds its next greater or smaller neighbour in one pass.
Daily Temperatures. For each day in temps, return how many days until a warmer temperature, or 0 if none comes.
Signals that point here
- "Next greater / next smaller element", to the left or right.
- Spans and waits: stock span, days until warmer.
- Largest rectangle in a histogram, trapping rain water, removing digits to make the smallest number.
The idea
Keep indices of days still waiting for a warmer day. Their temperatures are non-increasing from bottom to top, because a warmer day would already have resolved everything colder beneath it.
When today is warmer than the top, the top's wait is over: pop it and record i - j. Keep popping while that holds, then push today. Every index is pushed once and popped at most once.
def daily_temperatures(temps: list[int]) -> list[int]:
answer = [0] * len(temps)
stack: list[int] = [] # indices; temps non-increasing upward
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answerpublic static class MonotonicStack
{
public static int[] DailyTemperatures(int[] temps)
{
var answer = new int[temps.Length];
var stack = new Stack<int>(); // indices; temps non-increasing upward
for (int i = 0; i < temps.Length; i++)
{
while (stack.Count > 0 && temps[stack.Peek()] < temps[i])
{
int j = stack.Pop();
answer[j] = i - j;
}
stack.Push(i);
}
return answer;
}
}Complexity
O(n) time (each index pushed and popped at most once) and O(n) space.
Pitfalls interviewers watch for
- Storing values instead of indices, which loses the distance.
<=versus<: equal temperatures are not warmer. Decide strictness from the problem statement.- Calling it
O(n²)because of the nestedwhile. Explain the amortised argument instead.
Variants worth knowing
- Next greater element in a circular array: loop
2ntimes usingi % n. - Largest rectangle in a histogram: increasing stack; on pop, the popped bar's width runs from the new top to
i. - Sum of subarray minimums: previous-less and next-less boundaries from two stacks.
Test it like the interviewer will
daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])returns[1, 1, 4, 2, 1, 1, 0, 0]daily_temperatures([30, 40, 50, 60])returns[1, 1, 1, 0]daily_temperatures([30, 30, 30])returns[0, 0, 0]daily_temperatures([])returns[]- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- For each element, find the next greater element in a circular array.
- Find the largest rectangle in a histogram.
- Remove
kdigits from a number string to make it as small as possible.
Check yourself
Why is the stack monotone?
Any warmer day would already have popped every colder day below it, so the survivors are non-increasing.
Why is the nested loop linear overall?
Each index is pushed once and popped at most once, so total pops are at most n.