Daily Temperatures
Problem statement
You're given a list of daily temperature readings, temperatures — the
same shape as a stream of metric readings, like latency or CPU load, taken
once per day. For each day, find how many days you'd have to wait until a
warmer day comes along, and return those wait counts as an array. If no
warmer day ever comes for a given day, its wait count is 0.
Examples
Example 1
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation: Day 0 (73°) only has to wait 1 day for day 1's 74°. Day 2 (75°) has to wait 4 days, until day 6's 76°, since days 3–5 (71°, 69°, 72°) are all cooler or equal. The last two days (76° and 73°) never see anything warmer for the rest of the list, so they both get 0.
Example 2
Input: temperatures = [30,60,90]
Output: [1,1,0]
Explanation: Each day is immediately followed by a warmer one, except the last, which has nothing after it.
Hints
Approach
Optimal: Monotonic stack of indices
Intuition
Keep a stack of day indices that are still "waiting" for a warmer day, kept so their temperatures decrease from bottom to top. Walk the days left to right: whenever today's temperature beats the temperature at the index on top of the stack, that waiting day has just found its answer — the wait is today's index minus that day's index. Keep popping, since today might answer several waiting days in a row (a run of falling temperatures all broken by one warm day). Then push today's own index, since it's now waiting for its own warmer day.
Steps
- Create an
answerarray of zeros and an empty stack of indices. - For each index
i(with temperaturetemp = temperatures[i]):- While the stack isn't empty and the temperature at the stack's top
index is less than
temp: pop that indexj, and setanswer[j] = i - j. - Push
ionto the stack.
- While the stack isn't empty and the temperature at the stack's top
index is less than
- Anything left on the stack once the walk finishes never found a warmer
day, so its answer stays
0(already the default). - Return
answer.
Dry run
temperatures = [73, 74, 75, 71, 69, 72, 76, 73], stack starts empty:
| i | temp | pops (index → answer) | stack after |
|---|---|---|---|
| 0 | 73 | — | [0] |
| 1 | 74 | 0 → 1−0=1 | [1] |
| 2 | 75 | 1 → 2−1=1 | [2] |
| 3 | 71 | — | [2, 3] |
| 4 | 69 | — | [2, 3, 4] |
| 5 | 72 | 4 → 5−4=1, 3 → 5−3=2 | [2, 5] |
| 6 | 76 | 5 → 6−5=1, 2 → 6−2=4 | [6] |
| 7 | 73 | — | [6, 7] |
Indices 6 and 7 are left on the stack, so their answers stay 0. Result:
[1, 1, 4, 2, 1, 1, 0, 0], matching Example 1 exactly — including day 6
popping two waiting days in a single step.
Edge cases: a strictly decreasing list of temperatures never pops anything
— every day just gets pushed, and every answer stays 0. The last day in
the list is never popped either, since nothing comes after it to compare
against, so it always ends with 0.
Complexity
Time O(n) - each index is pushed onto the stack once and popped at most once across the whole walk through `temperatures`.
Space O(n) - for the stack and the output array.
from typing import List
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
stack: List[int] = [] # indices still waiting for a warmer day
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer
if __name__ == "__main__":
print(Solution().dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])) # [1, 1, 4, 2, 1, 1, 0, 0]
print(Solution().dailyTemperatures([30, 60, 90])) # [1, 1, 0]RecapThe whole problem in a few lines, for the night before
- Spot it: "for each position, how many steps away is the next bigger value" — a monotonic-stack distance variant
- Idea: keep a decreasing stack of indices waiting for a warmer day; when today beats the stack's top, pop it and record today's index minus that day's index
- Cost: O(n) time, O(n) space for the stack and output
- Trap: rescanning forward from every index instead of reusing the stack gives O(n²) — the same trap as Next Greater Element I's brute force
Interview follow-ups
What if you needed the day with the *largest* temperature increase, not just the first warmer day?
That's a different question — you'd need to compare against every later day's temperature rather than stopping at the first one that's bigger, which brings back an O(n²) scan unless a structure like a suffix maximum is precomputed to answer "what's the highest temperature from here onward" in O(1) per query.
How would this work in a streaming setting, where new days keep arriving and earlier answers need to stay final once they're set?
The same monotonic stack works online without changes: process each new day's temperature as it arrives, pop and finalize any waiting days it beats, then push the new day. Every day's answer becomes final the instant a warmer day appears after it, so nothing ever needs to be revisited once it's popped.
Frequently asked questions
Because the answer needed is a distance in days, not a temperature value, and that distance only comes from subtracting index positions. The temperature at any stored index is still just one array lookup away whenever it's needed for a comparison, so nothing is lost by storing the index instead.
Both ask "what's the first bigger value to the right of this one," resolved with the same decreasing monotonic stack. The only real difference is what gets recorded the moment a match is found — a distance in days here, versus the actual value there.
Given a stream of readings — latency, queue depth, CPU load — "how many time steps until this reading is exceeded" is exactly the shape of a lookahead question used to spot a worsening trend or estimate when a threshold will next be crossed.
Neither day counts as "warmer" for the other, since the comparison is strict (>, not >=). A tie never triggers a pop, so both days keep waiting on the stack for a later day that's genuinely higher, not just equal.
