Daily Temperatures

1. Problem & Core Objective

The problem

Given an array temperatures where temperatures[i] is the temperature on day i, return an array answer such that answer[i] is the number of days you have to wait after day i to get a warmer temperature.

If no future day is warmer, answer[i] = 0.

Input:  temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Input:  temperatures = [30,40,50,60]      Output: [1,1,1,0]
Input:  temperatures = [30,60,90]         Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

What the interviewer is actually testing

This is the canonical monotonic stack problem. If you can only rehearse one from this section, rehearse this.

1. Do you recognize "next greater element" as a monotonic stack? The phrasing is disguised — "how many days until warmer" — but it's the standard shape.
2. Can you prove the amortized O(n)? The while inside the for looks quadratic. "Each index is pushed once and popped at most once" is the required answer, and it's asked essentially every time.
3. Do you store indices rather than temperatures? The answer is a distance, which you can only compute if you know where each waiting day was.
4. Do you notice the bounded temperature range? 30..100 is only 71 values, which enables a genuinely different O(n · 71) solution — worth mentioning as evidence you read the constraints.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^5.

• O(n²) → 10^10. Too slow.
• O(n) → the target.

The temperature range is 30 to 100 — only 71 distinct values. That's unusually narrow, and it's a hint that an alternative approach exists (§3, Approach 4).

Step 2 — Brute force, and the observation that matters

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (temperatures[j] > temperatures[i]) { answer[i] = j - i; break; }

O(n²). Now look at what actually happens during a scan.

Take [73, 74, 75, 71, 69, 72, 76, 73] and stand at day 5 (72°). Looking back:

• Day 4 (69°) is still waiting for a warmer day. 72 answers it.
• Day 3 (71°) is also still waiting. 72 answers it too.

One arriving element resolved two waiting days at once. The brute force would have discovered each independently, rescanning the same region twice.

Step 3 — The stronger observation: permanent irrelevance

Now look further back. Day 2 is 75°, and day 3 is 71°.

Can day 3 (71°) ever be the answer to a query about something further left? No — but more importantly, once day 5 (72°) resolves day 3, day 3 can be discarded forever. It has its answer and will never be consulted again.

And there's a second kind of discard. Consider days 3 (71°) and 4 (69°). Any future day warm enough to resolve day 3 is also warm enough to resolve day 4 — since 69 < 71. But day 4 is later, so it must be resolved first or simultaneously. The ordering is forced.

Keep a collection of days still waiting for an answer, maintained in decreasing temperature order. An arriving warmer day pops every waiting day it beats, from the most recent backwards.

That's a monotonic decreasing stack.

Step 4 — Why decreasing, specifically

Ask the diagnostic question: what event finally lets me answer for a day I already passed?

A warmer day arriving. So the pop trigger is "a larger element arrives", and by the table in the section README that means the stack holds decreasing values.

If the stack ever held an increasing pair — a cooler day below a warmer one — the cooler one would already have been resolved by that warmer one. So decreasing order is maintained automatically by the popping rule; it's an invariant, not something you enforce separately.

Step 5 — Why indices, not temperatures

The answer for day i is j - i — a distance. You need both positions.

If the stack stored temperatures alone, popping would tell you "this waiting day is resolved" but not which day it was, so you couldn't write to answer[i] or compute the gap.

Store indices; get the temperature via temperatures[index] whenever needed.

Step 6 — Why it's O(n)

Each index is pushed exactly once (at its own iteration) and popped at most once (after which it never returns). So across the entire run, the inner while body executes at most n times in total.

The inner loop doesn't multiply the outer one — it consumes from a budget of n pushes. Total work is O(n).

3. Solution Paths

Approach 1 — Brute force

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (temperatures[j] > temperatures[i]) { answer[i] = j - i; break; }
        }
    }
    return answer;
}

answer is zero-initialized, so days with no warmer future need no explicit handling.

• Time: O(n²) — worst case a strictly decreasing array, where every scan runs to the end.
• Space: O(1) beyond the output.

Counter-questions on this approach

⭐ "What's the worst-case input, and how bad is it?"

A strictly decreasing array like [100, 99, 98, …]. Every day scans to the end and finds nothing, giving n²/2 comparisons — about 5 × 10^9 at n = 10^5. That's the shape to name, because it shows the bound is real rather than theoretical.

"When you scan forward from day i and pass several cooler days, are you learning anything about them?"

Yes, and discarding it. Those cooler days are also waiting for a warmer day, and whatever eventually resolves day i may resolve them too. The brute force rediscovers that for each one independently. Carrying the waiting days forward in a structure is what removes the repetition.

Approach 2 — Monotonic stack (optimal)

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();     // holds INDICES; their temps decrease

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int idx = stack.pop();
            answer[idx] = i - idx;                 // DISTANCE, not temperature
        }
        stack.push(i);
    }
    return answer;                                 // unresolved indices keep their default 0
}

Full trace on [73, 74, 75, 71, 69, 72, 76, 73]:

Result: [1, 1, 4, 2, 1, 1, 0, 0] ✓

Notice step i = 5: the arriving 72° resolved two waiting days in one iteration. And indices 6 and 7 are left on the stack at the end — they never found a warmer day, so their answers stay 0.

• Time: O(n) — amortized; see the counter-questions.
• Space: O(n) — worst case a strictly decreasing array pushes everything.

Counter-questions on this approach

⭐ "There's a while inside a for. Prove this isn't O(n²)."

Each index is pushed onto the stack exactly once, at its own iteration of the outer loop. It can be popped at most once, and once popped it never returns. So across the entire run, the total number of pop operations is bounded by n.

The inner while doesn't multiply the outer loop — it consumes from a fixed budget of n pushes. Some single iterations pop fifty items, but then fifty later iterations pop nothing. Total work is n pushes + at most n pops = O(n).

That's aggregate accounting: bound the total work over the whole run, not the worst case of one iteration.

⭐ "Why store indices rather than temperatures?"

Because the answer is a distance, i - idx. If the stack held temperatures alone, popping would tell me a waiting day is resolved but not which day — so I couldn't write to answer[idx] or compute the gap. Indices give me both: the position directly, and the temperature via temperatures[idx].

"Why is the stack decreasing? Do you enforce that anywhere?"

It's maintained automatically by the popping rule, not by a separate check. Before pushing i, the while loop removes everything with a smaller temperature — so whatever remains is strictly greater than temperatures[i], and pushing i keeps the sequence decreasing. The invariant is a consequence of the algorithm rather than an extra condition.

"You use < in the pop condition. What about equal temperatures?"

With <, equal temperatures are not popped — which is correct, because the problem asks for a strictly warmer day. On [73, 73] the second 73 doesn't resolve the first, so both correctly get 0. Using <= would wrongly report a wait of 1. That's a real correctness detail, not a style choice.

"What about the indices left on the stack when the loop ends?"

They never found a warmer day, so their answers should be 0 — and new int[n] is already zero-filled, so there's nothing to do. Worth stating explicitly that I relied on Java's default initialization rather than leaving it implicit.

Approach 3 — Backward scan with jumping

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];

    for (int i = n - 2; i >= 0; i--) {
        int j = i + 1;
        while (j < n && temperatures[j] <= temperatures[i]) {
            if (answer[j] == 0) { j = n; break; }      // day j never warms — nor will i
            j += answer[j];                            // JUMP over j's known wait
        }
        if (j < n) answer[i] = j - i;
    }
    return answer;
}

How it works. Fill from the right. When day j isn't warm enough for day i, don't step to j + 1 — jump directly to the day that resolved j, since everything between them is no warmer than j.

• Time: O(n) amortized in practice, though the bound is harder to argue rigorously.
• Space: O(1) beyond the output — no stack at all.

Counter-questions on this approach

⭐ "This uses O(1) extra space. Why isn't it the preferred answer?"

Two reasons. Its complexity argument is much weaker — the jumping is fast in practice but the amortized bound isn't as clean as "each index is pushed once and popped once", and I'd struggle to prove O(n) rigorously under questioning. And the stack's O(n) space is only reached on a strictly decreasing array, which is a narrow worst case. Given that the stack version is easier to prove and easier to read, I'd ship it and mention this as the space-optimal alternative.

"Why does answer[j] == 0 mean you can stop entirely?"

Because answer[j] == 0 means no day after j is warmer than j. And since temperatures[j] >= temperatures[i] at that point, nothing after j can be warmer than i either. So day i has no answer, and I break out rather than scanning the rest.

Approach 4 — Bucket by temperature

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    int[] nextOccurrence = new int[101];           // temperature -> earliest later day with it
    Arrays.fill(nextOccurrence, Integer.MAX_VALUE);

    for (int i = n - 1; i >= 0; i--) {
        int earliest = Integer.MAX_VALUE;
        for (int t = temperatures[i] + 1; t <= 100; t++) {    // any strictly warmer temperature
            earliest = Math.min(earliest, nextOccurrence[t]);
        }
        if (earliest != Integer.MAX_VALUE) answer[i] = earliest - i;
        nextOccurrence[temperatures[i]] = i;
    }
    return answer;
}

How it works. Scanning right to left, remember the earliest upcoming day for each temperature value. For day i, the answer is the nearest among all temperatures strictly above temperatures[i].

• Time: O(n · 71) = O(n), since the temperature range is fixed at 30–100.
• Space: O(1) — 101 ints.

Counter-questions on this approach

⭐ "Is O(n · 71) really O(n)?"

Yes — 71 is a constant fixed by the problem's stated temperature range, not a function of the input. But it's a large constant, and the stack version does genuinely less work: n pushes and at most n pops, versus 71 comparisons per element. I'd present the stack as the answer and mention this as evidence I read the constraints.

"When would this be the better choice?"

If the values were even more tightly bounded, or if I needed to answer repeated queries against a fixed array — the nextOccurrence table generalizes to "next day at least as warm as T" for arbitrary T, which the stack doesn't give you for free.

Comparison

4. Why the Optimal Wins

Against brute force. The brute force rediscovers, for each day independently, information it already encountered. The stack carries the unresolved days forward, so an arriving warm day resolves all of them at once — in the trace above, one element at i = 5 answered two queries.

Against the jumping version. Both are effectively O(n), and jumping wins on space. But the stack's complexity argument — each index pushed once, popped at most once — is airtight and stateable in one sentence, while the jumping bound requires a subtler amortization argument. Under questioning, the provable one is worth more than the marginally leaner one.

Against buckets. Also O(n) but with a constant of 71. The stack does strictly less work.

Why O(n) is the floor. Every temperature must be read, and there are n answers to write. So O(n) is optimal.

The transferable pattern — this is the reusable takeaway:

"Next greater element" problems are monotonic stacks. Keep the unresolved items in sorted order; an arriving item resolves everything it dominates, all at once.

The same template, with res[idx] = temperatures[i] instead of i - idx, solves Next Greater Element directly. With an increasing stack instead, it solves Largest Rectangle in Histogram.

5. Java Prerequisites

ArrayDeque as a stack

Deque<Integer> stack = new ArrayDeque<>();
stack.push(i);        // addFirst
stack.pop();          // removeFirst — throws if empty
stack.peek();         // peekFirst — null if empty
stack.isEmpty();

Use ArrayDeque, not java.util.Stack (legacy synchronized Vector). See 02 §5.

Arrays are zero-initialized

int[] answer = new int[n];     // all zeros — exactly the "no warmer day" answer

Days left on the stack need no cleanup. Relying on this is fine; say that you're relying on it rather than leaving a reader to wonder whether you forgot.

Guard before peeking

while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i])

&& short-circuits, so stack.peek() is never called on an empty deque. Reversing the operands would throw a NullPointerException when the auto-unboxing of null occurs.

Autoboxing

stack.push(i);                      // int → Integer
temperatures[stack.peek()]          // Integer → int for the array index

Both implicit. The unboxing in the array index would throw if peek() returned null, which is why the isEmpty() guard must come first.

For allocation-free code, a hand-rolled int[] stack with a top index avoids boxing entirely — worth mentioning, rarely worth writing.

< versus <= in the pop condition

temperatures[stack.peek()] < temperatures[i]     // strictly warmer — correct
temperatures[stack.peek()] <= temperatures[i]    // would resolve EQUAL temperatures — wrong

The problem asks for a warmer day, not "at least as warm". [73, 73] must give [0, 0].

6. Interview Communication Guide

Clarifying questions

1. "Does 'warmer' mean strictly greater, or at least as warm?" — strictly greater, which decides < versus <= in the pop condition.
2. "What should answer[i] be when no warmer day exists?" — 0, which Java's array initialization gives for free.
3. "Is the temperature range really bounded at 30–100?" — yes, and it enables an alternative solution worth mentioning.
4. "Can there be duplicate temperatures?" — yes, and they must not resolve each other.
5. "Do I return distances or indices?" — distances, j - i.

The pitch

"For each day I need the number of days until a strictly warmer one — that's a 'next greater element' problem.

Brute force scans forward from each day, which is O(n²) and hits 10^10 on a decreasing array.

The key observation: when I'm standing on a warm day and look back, there may be several cooler days still waiting for an answer — and this one day resolves all of them at once. So instead of rescanning, I'll keep the unresolved days in a stack, maintained in decreasing temperature order.

When a day arrives, I pop every waiting day with a lower temperature and set its answer to the distance. Then I push the current day.

I store indices, not temperatures, because the answer is a distance — I need to know which day I'm resolving and how far back it was.

On complexity: there's a while inside the for, but it's O(n). Each index is pushed exactly once and popped at most once, so across the whole run the inner loop body runs at most n times total. It consumes a budget of n pushes rather than multiplying the outer loop.

Days still on the stack at the end never found a warmer day, and new int[n] is already zero-filled, so that's handled.

One more thing worth noting — the temperature range is only 30 to 100, so there's an alternative that buckets by temperature and runs in O(71n). The stack does less work, but it's good evidence the narrow range is deliberate."

Edge cases to raise proactively

The all-equal case is the one to volunteer — it's what distinguishes < from <= in the pop condition, and a solution using <= silently returns [1,1,0].

The strictly decreasing case is the second: it's the worst case for space (the stack reaches size n), and it proves the space bound is O(n) rather than O(1).

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Next Greater Element in a circular array." (LC 503)

Iterate 2n times using i % n for indexing, so elements can wrap around and find a greater element earlier in the array. Only push indices during the first pass — the second pass exists purely to resolve leftovers. Still O(n) time and space, and a clean demonstration that the stack template survives the change untouched.

"Return the warmer temperature rather than the number of days."

Change one line: answer[idx] = temperatures[i] instead of i - idx. Same structure — which is exactly why storing indices was the right call, since it leaves both options open.

"Find the previous warmer day instead of the next one."

Either iterate right to left with the same template, or keep the left-to-right scan and record the answer at push time rather than pop time — the element below you on the stack is the previous greater. Both O(n).

"What if the array were enormous and streamed in — you can't hold it?"

The stack version already works: it holds only unresolved indices and never looks backwards into the array beyond those. Store the temperature alongside each index so you don't need to dereference the original array. Memory becomes O(unresolved) rather than O(n) — and on mostly-increasing data that's tiny.

"What if you needed the answer for an arbitrary threshold T, not just 'warmer than today'?"

The stack doesn't help, because it's built around a fixed comparison. The bucket approach generalizes though: the nextOccurrence table answers "next day with temperature ≥ T" for any T in O(71). That's the case where the bucket version earns its keep.

"What if temperatures could be updated after the fact?"

The stack is a one-pass construction and can't handle updates. You'd need a segment tree supporting "first index to the right with value > x", giving O(log n) per query and update. Worth stating plainly that the monotonic stack doesn't apply once the array is mutable.