#739 Daily Temperatures

frequently reported atByteDance / TikTok Amazon Bloomberg Microsoft Google Meta

the problem

In plain words

Given daily temperatures, return an array where answer[i] is how many days you must wait after day i for a warmer temperature. If no warmer day comes, answer[i] = 0.

in temperatures = [73,74,75,71,69,72,76,73]

out [1,1,4,2,1,1,0,0]

in temperatures = [30,60,90]

out [1,1,0]

1 ≤ n ≤ 10⁵
30 ≤ temperatures[i] ≤ 100

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternMonotonic stack

This is next-greater-element asking for a distance. Keep waiting days (indices) on a decreasing stack; a warmer day pops and answers all colder days on top.

solutions

From brute force to optimal

For each day, walk right until a warmer day appears.

For each i, for j = i+1.. while temperatures[j] ≤ temperatures[i].
answer[i] = j − i, or 0 if none.

timeO(n²)

A decreasing input makes every day scan to the end.

spaceO(1) extra

Only the output array.

javajava.util.*

1class Solution {2    public int[] dailyTemperatures(int[] temperatures) {3        int n = temperatures.length;4        int[] answer = new int[n]; // 0 = no warmer day5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                if (temperatures[j] > temperatures[i]) { answer[i] = j - i; break; }8            }9        }10        return answer;11    }12}

Days wait on the stack. Today pops every colder day on top and fills in their wait as today − thatDay.

For each day i:
while the stack is non-empty and temperatures[top] < temperatures[i]: pop j, answer[j] = i − j.
push i.
Days left on the stack keep 0.

timeO(n)

Each day is pushed once and popped at most once.

spaceO(n)

A falling temperature run keeps every day on the stack.

javajava.util.*

1class Solution {2    public int[] dailyTemperatures(int[] temperatures) {3        int n = temperatures.length;4        int[] answer = new int[n];5        Deque<Integer> stack = new ArrayDeque<>(); // days still waiting; temps decrease bottom -> top6        for (int i = 0; i < n; i++) {7            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {8                int day = stack.pop();9                answer[day] = i - day;10            }11            stack.push(i);12        }13        return answer; // days left on the stack never warm up: 014    }15}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int[] dailyTemperatures(int[] temperatures) {3        int n = temperatures.length;4        int[] answer = new int[n];5        Deque<Integer> stack = new ArrayDeque<>(); // days still waiting; temps decrease bottom -> top6        for (int i = 0; i < n; i++) {7            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {8                int day = stack.pop();9                answer[day] = i - day;10            }11            stack.push(i);12        }13        return answer; // days left on the stack never warm up: 014    }15}

Go right to left. To find day i's warmer day, start at i+1 and hop along answers you already computed.

Track the hottest temperature seen so far (from the right). If today is the hottest, answer is 0.
Otherwise days = 1; while temperatures[i + days] ≤ today: days += answer[i + days].
answer[i] = days.

timeO(n)

The days you hop over are exactly what a monotonic stack would pop; each is hopped over for at most one later day, so hops total O(n).

spaceO(1) extra

Reuses the output array — no stack.

javajava.util.*

1class Solution {2    public int[] dailyTemperatures(int[] temperatures) {3        int n = temperatures.length;4        int[] answer = new int[n];5        int hottest = 0;6        for (int i = n - 1; i >= 0; i--) {7            int t = temperatures[i];8            if (t >= hottest) { hottest = t; continue; } // nothing warmer to the right9            int days = 1;10            while (temperatures[i + days] <= t) {11                days += answer[i + days]; // jump straight to that day's warmer day12            }13            answer[i] = days;14        }15        return answer;16    }17}

in the room

How to say it in the interview

talk track

Name the pattern: "this is next greater element, returning distance instead of value."
State the invariant: "the stack holds days with no warmer day yet; their temperatures decrease upward."
Give the amortized argument for O(n).
Offer the backward-jump version if asked for O(1) extra space.

traps

Using <= in the pop condition: an equal temperature is not warmer, so it must not pop.

what they ask next

Follow-ups

Online Stock Span (LC 901)?

It asks for the previous strictly greater price, answered on push: keep (price, span) pairs on a decreasing stack, pop every price ≤ today and add up their spans.

Next Greater Element II (LC 503) — circular array?

Loop i from 0 to 2n − 1 and use i % n; only push during the first pass.

before you submit

Edge cases to test

Equal temperatures are not warmer: [70, 70, 71] → [2, 1, 0].
A falling run keeps every day waiting: [90, 80, 70] → [0, 0, 0].
The last day always gets 0.

practise next