Pattern this teaches:Monotonic Stack
Daily Temperatures
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
Given a list of daily temperatures, return an array where each element tells you how many days you must wait until a warmer temperature occurs. If there is no future day with a warmer temperature, the value is 0.
Example 1
- Input
- temperatures = [30,35,25,40,45]
- Output
- [1,2,1,1,0]
- Why
- Day 0 waits 1 for 35. Day 1 waits 2 for 40. Day 2 waits 1 for 40. Day 3 waits 1 for 45.
Example 2
- Input
- temperatures = [60,55,50,45,40]
- Output
- [0,0,0,0,0]
- Why
- Strictly decreasing, no warmer day ahead.
Constraints
- 1 <= temperatures.length <= 10^5
- 30 <= temperatures[i] <= 100
How to think about it
Updated 2026-09-29Days waiting for a warmer temperature are unresolved promises. Walking left to right, each day cannot know its answer until a strictly warmer day arrives to settle it. A stack holding indices of unresolved days in strictly decreasing temperature order lets any warmer day immediately resolve and pop every colder day waiting behind it.
Approaches, worst first
Forward quadratic scan
time O(n^2) · space O(1)
For each day i, walk j from i + 1 to the end of the array looking for the first temperature strictly greater than temperatures[i]. If found, record j - i, otherwise leave 0. Suffers worst-case quadratic time when temperatures are sorted in non-increasing order.
Monotonic decreasing stack of indicesWrite this one
time O(n) · space O(n)
Iterate through days using an index stack. While the stack is non-empty and the current temperature exceeds the temperature at the stack top index, pop that index and write the difference `i - poppedIndex` into the answer array. Push the current index. Each index is pushed and popped at most once.
Where people lose marks · 3
- Pushing temperatures instead of indices onto the stack leaves you unable to compute the elapsed day distance `i - prevIndex` when a match is found.
- Using `>=` instead of `>` when popping colder days incorrectly pops equal temperatures, violating the requirement that the future day must be strictly warmer.
- Leaving unresolved days uninitialized: the result array must default to 0 so days that never encounter a warmer future day correctly report 0.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .