Skip to main content
DSA patterns

Daily Temperatures

mediumStack and queue Must-doMetaAppleSalesforce

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

Hint 1: For each day, you're looking for the first day afterward with a higher temperature — the same "next greater" question you'd ask of any array, except this time the answer is a distance (in days), not the value itself.

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

  1. Create an answer array of zeros and an empty stack of indices.
  2. For each index i (with temperature temp = temperatures[i]):
    1. While the stack isn't empty and the temperature at the stack's top index is less than temp: pop that index j, and set answer[j] = i - j.
    2. Push i onto the stack.
  3. Anything left on the stack once the walk finishes never found a warmer day, so its answer stays 0 (already the default).
  4. 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.