An HVAC ops dashboard for a cold-storage warehouse plots daily highs so facilities can see how long today’s cooling load lasts before a warmer day changes the plan. The intern nested a scan: for each day i, walk i+1, i+2, … until a strictly warmer reading. A month of highs returned in milliseconds. Three years of daily readings were still looping when the dashboard timed out.

Daily Temperatures asks how many days you wait for a strictly warmer high. A nested forward scan uses that and still pays O(n²). The wait is later index minus earlier index; sorting would destroy the day order that subtraction needs.

This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about a decreasing stack of indexes so the wait is subtraction, not a restart.

The problem

Given an int[] temperatures of daily highs, return an int[] answer the same length. answer[i] is the number of days you wait after day i for a later day whose high is strictly warmer. If no such day exists, answer[i] is 0.

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]  →  [1, 1, 4, 2, 1, 1, 0, 0]
temperatures = [80, 70, 70, 75]                    →  [0, 2, 1, 0]

Day 2 in the first row (75) waits until index 6 (76): wait is 6 - 2 = 4, not the temperature. The second row is the equal-high trap: 70 does not resolve 70. Only 75 does.

Note: The return is waits, not the next warmer value. If they wanted the value, the same walk works and the arithmetic changes. Do not mix the two prompts.

Nested forward scan is the honest brute force

From each i, walk right until you find a strictly larger high, store j - i, and leave 0 if you miss. Correct. Quadratic.

int[] dailyTemperaturesNested(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;
}

At n = 30 this is a rounding error. At a few years of daily highs you paid a nested scan for a question a stack answers because each day is a candidate for many earlier days at once: is today warmer than the day still waiting on top?

Decreasing stack of waiting-day indexes

The stack holds indexes of days that still have no warmer successor. Temperatures at those indexes are decreasing from bottom to top — a monotonic decreasing stack. Walk left to right. Today is i.

  • While the stack is not empty and temperatures[i] is strictly warmer than temperatures[days.peek()], pop j and set answer[j] = i - j.
  • Push i. It is now the newest day still waiting.

Days left on the stack at the end never found a warmer successor. They already hold 0 if you allocated new int[n].

Walk the first sample. Stack contents are indexes; the highs are only for the comparison.

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

i=0  73   []              push 0                 [0]
i=1  74   73<74  pop 0    answer[0]=1            [1]
i=2  75   74<75  pop 1    answer[1]=1            [2]
i=3  71   75>71           push 3                 [2, 3]
i=4  69   71>69           push 4                 [2, 3, 4]
i=5  72   69<72  pop 4    answer[4]=1
          71<72  pop 3    answer[3]=2  push 5    [2, 5]
i=6  76   72<76  pop 5    answer[5]=1
          75<76  pop 2    answer[2]=4  push 6    [6]
i=7  73   76>73           push 7                 [6, 7]

leftover [6, 7] stay 0
answer = [1, 1, 4, 2, 1, 1, 0, 0]

Index 5 (72) resolved two waiters in one step. Index 6 (76) resolved two more. That is the whole saving: one later day closes every earlier day it dominates, and you never rescan them.

The Java is that walk. The stack stores indexes, not highs.

int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> days = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!days.isEmpty() && temperatures[i] > temperatures[days.peek()]) {
            int j = days.pop();
            answer[j] = i - j;
        }
        days.push(i);
    }
    return answer;
}

Time is O(n) — each index is pushed once and popped at most once. Space is O(n) for the stack (strictly decreasing highs never pop until the end). Do not quote the nested O(n²) as the intended bill.

Store indexes, not temperatures. A stack of highs can tell you that a warmer day arrived; it cannot tell you how many days you waited. Equal highs do not pop — the wait needs a strictly warmer day, so 70 on top of 70 stays until a later 75.

What interviewers usually poke next

  • Next greater values, not waits. Same decreasing stack of indexes; the payload is temperatures[i] (or both) instead of i - j. Say the arithmetic changed. Do not rewrite this method into that one.
  • Same monotonic family. Car Fleet and Largest Rectangle in Histogram use the same index-stack idea. Do not solve them on this prompt.
  • Circular array. Next greater wrapping around is two passes over the same idea, not a new ADT. Do not invent a second stack.
  • Next smaller. Flip > to <. The index stack and the i - j wait stay the same shape.
  • Right to left. Push from the end so a warmer day is already on the stack when you look. Same O(n); easier to botch the wait because the later index is the one already stored.

You are done with this problem when you can walk [73, 74, 75, 71, 69, 72, 76, 73] out loud, pop two indexes at 72 and two at 76, and say why a stack of values cannot return the waits.