vizlearn

Daily temperatures, and the monotonic stack

Interview QuestionsBy Updated

Keep a stack of indices whose answer is not known yet, with temperatures decreasing from the bottom. When a warmer day arrives it resolves every index it beats, popping them. Each index is pushed once and popped at most once, so the nested loop is still O(n).

Stacks & queuesCoding problemMedium

Step through it

What to watch

  • 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.

Say this 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."

Overview

For each temperature, find the next strictly warmer day. A decreasing stack of unresolved day indices lets each new day answer several earlier queries, giving linear total work even though the code contains a nested loop.

Run it

The brute force and the stack, with their operation counts.

1Python
Output
The shape that looks worst for the inner loop - and the 2n bound as a number.
2Python
Output
And the decision the problem statement usually leaves out.
3Python
Output

                

                

                    
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.

                

                

                    
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. This 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.

                

                

                    
Sources and next steps

                    
                

            


        

    



How the code works
The brute force and the stack side by side with their operation counts, then the 2n bound measured on a 2,000-element worst case.
How the code works
  1. while stack and temps[stack[-1]] < tThe day on top of the stack is the most recent unresolved one. If today beats it, its answer is known now — and possibly the one beneath it too, which is why this is a loop.
  2. out[j] = i - jThe stack holds indices precisely so this subtraction is available. Storing temperatures instead loses the distance, which is the answer being asked for.
  3. pushes + popsThe amortised argument, as a number. Each index enters once and leaves at most once, so this total is bounded by 2n regardless of the input's shape.
  4. while stack and temps[stack[-1]] <= tThe loose variant, printed on a run of equal temperatures. Whether equal counts as warmer is a question to ask, not to assume.
Change one thing
  • Reverse the comparison to > and you have "days until a colder temperature" — the same code, an increasing stack, a different question.
  • 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.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. What does the stack hold?
  2. Why is the algorithm O(n) despite a while loop inside a for loop?
  3. What happens to indices still on the stack at the end?
  4. To find the next SMALLER element instead, you would:




        
    



 Cheat sheet
Daily temperatures, and the monotonic stack
Solve daily temperatures with a monotonic stack. Watch the stack shrink as each warmer day resolves earlier entries, and see why one pass is enough.
INTERVIEW · vizlearn.in/interview/daily-temperatures.html
More in Interview
InterviewImplement a queue using two stacksInterviewTop k frequent elementsInterviewMerge k sorted sequencesInterviewFind the median of a data stream
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact