Run it
The brute force and the stack, with their operation counts.
The shape that looks worst for the inner loop - and the 2n bound as a number.
And the decision the problem statement usually leaves out.
The question behind the question
"Days until something bigger" is the next greater element problem, and recognising it is most of the value here. The brute force is a scan forward from every position, O(n²), and it is doing the same comparisons over and over.
The insight is to invert it. Instead of asking each day to look forward for its answer, let each day announce itself to the days still waiting. A day is waiting precisely because nothing warmer has arrived, which means the waiting days are in decreasing order of temperature — and a decreasing sequence you only ever append to or trim from the end is a stack.
Why the nested loop is not quadratic
This is the part interviewers probe, because the code has a while inside a for and looks O(n²).
Count the work by element rather than by iteration. Each index is pushed exactly once. Each index is popped at most once, and once popped it never returns. So the total number of stack operations across the whole run is at most 2n, whatever the shape of the input — the inner loop can be long on one iteration only by being empty on others.
The editor below prints the push and pop counts, including for a 2,000-element worst case, so the 2n bound is a number rather than an assertion. This accounting argument is called amortised analysis, and naming it is worth doing.
Decreasing or increasing, and strict or not
Two decisions define the variant, and they are where the off-by-one errors live.
Direction. A decreasing stack finds the next greater element; an increasing stack finds the next smaller one. The comparison in the while is the only thing that changes.
Strictness. < versus <= decides what happens on equal values — whether "warmer" means strictly warmer. With < an equal temperature does not resolve the earlier day, which is the usual reading of this problem. If the interviewer says "at least as warm", it flips.
Where else this shape appears
Once the pattern is visible it is everywhere: the largest rectangle in a histogram, trapping rain water, the stock span problem, sliding-window maximum (with a deque rather than a stack), and removing k digits to make the smallest number. All of them keep a monotonic sequence of candidates and discard the ones that a new arrival has made irrelevant.
The tell, in any problem statement: "the next" or "the previous" element that is bigger or smaller. That phrasing is the monotonic stack asking to be used.
What to say out loud
A monotonic decreasing stack of indices. For each day I pop every index whose temperature is lower than today's and record the difference as their answer, then push today. Each index is pushed and popped at most once, so it is O(n) time and O(n) space - the inner while loop does not make it quadratic.
Edge cases to raise
Volunteering these is most of what separates a correct answer from a good one.
Equal temperatures. Whether "warmer" is strict decides the answer, and the problem statement often does not say. Ask, or state your assumption - the editor prints both variants on a run of equal values.
The answer array is the output, not the stack. A common slip is to build the result by appending as things resolve, which produces the answers in resolution order rather than by day.
Space is O(n) in the worst case - a strictly decreasing input leaves every index on the stack until the end. If the interviewer asks for O(1) space, this approach cannot give it and the honest answer is that the brute force is the only O(1)-space option.
The follow-ups interviewers ask
"What is the largest rectangle in a histogram?" The same stack with the comparison arranged so a shorter bar resolves the taller ones behind it, and the width comes from the index difference. It is the hardest of this family and it is the standard escalation from this question.
"Sliding-window maximum." A monotonic deque rather than a stack, because entries leave from both ends: the front when it falls out of the window, the back when a bigger arrival makes it irrelevant. Same discard rule, one more exit.
"Can you do it right to left instead?" Yes, and some people find it easier: walk backwards, popping anything not warmer than the current day, and the answer for each day is the index left on top. Same complexity, same structure, and worth knowing because half the published solutions are written that way.
Common wrong answers
"The while inside the for makes it O(n2)." The commonest wrong answer, and the one the question exists to test. Count by element: each index is pushed once and popped at most once, so the total is bounded by 2n.
"Store temperatures on the stack." Then you cannot compute the distance, which is the thing being asked for. Indices carry both the value (via a lookup) and the position.
"Sort the temperatures first." Sorting destroys the order, and the answer is entirely about order. Any solution that begins by sorting has answered a different question.
Recap in one screen
- The stack holds indices, not temperatures - the answer is a distance.
- One warm day can resolve several waiting days at once.
- Anything still on the stack at the end never found a warmer day, so it stays 0.
- Worth trying: Reverse the comparison to > and you have "days until a colder temperature" - the same code, an increasing stack, a different question.
- Worth trying: Return the index of the next warmer day instead of the distance. One character changes, and it is the version most other next-greater-element problems actually want.