Free lesson · DSA Mastery - Interview Prep, End to End

Daily Temperatures

Medium6 min readdsastacks

Daily Temperatures

Daily Temperatures introduces the distance archetype of the monotonic stack: instead of the next greater value, you report how many days you must wait until a warmer temperature. The only change from the Next Greater Element template is what you store and what you compute on a pop - you store indices and, when an element resolves, the answer is currentIndex - poppedIndex. This problem cements why monotonic stacks so often hold indices rather than values: indices let you measure how far, not just what. We present the brute force for contrast and the index-based monotonic stack as the optimal solution.

The reframe is small but pivotal: "next greater element" and "days until warmer" are the same computation. The stack still pops smaller tops when a larger value arrives; the difference is that on each pop you record a distance instead of a value.

Interactive animation: Step through Daily Temperatures yourself: every approach, frame by frame, on the lesson's own examples.

The Problem

Interactive animation: How long does each day wait?

Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	Brute force (scan forward per day)	O(n²)	O(1)	Baseline
2	Monotonic decreasing stack of indices	O(n)	O(n)	Optimal

Brute force scans forward from each day for a warmer one. The monotonic stack - the Next Greater template storing indices and computing distances on pop - answers everything in one pass.

Interactive animation: Same answers, and almost the same bill.

Approach 1: Brute Force

The Idea

For each day i, scan forward until you find a warmer day j, recording j - i; if none, leave 0. Quadratic in the worst case (e.g. a long descending run).

Logic Flowchart

graph TD
    A["for each day i"] --> B["scan j = i+1 .. end"]
    B --> C{"temp[j] > temp[i]?"}
    C -->|Yes| D["answer[i] = j - i; stop"]
    C -->|No| E{"more j?"}
    E -->|Yes| B
    E -->|No| F["answer[i] = 0"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows the brute force. For each day we scan forward to the first warmer day and record the gap, or zero if none. A long cooling streak makes this quadratic.

Code

public static int[] dailyTemperaturesBrute(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;
}

This Java code scans forward from each day for the first warmer temperature, recording the day gap or leaving zero. It is quadratic in the worst case.

Complexity

Time: O(n²). Space: O(1) beyond output.

Approach 2: Monotonic Decreasing Stack of Indices - Optimal

Interactive animation: Every pop answers a bar that was waiting - The pop tells you WHO answers whom. The index gap tells you how far.

The Idea

Keep a stack of indices of days still waiting for a warmer day, with temperatures decreasing from bottom to top. For each day i:

While the stack is non-empty and temperatures[i] > temperatures[stack.peek()], day i is warmer than that top - pop it and set answer[popped] = i - popped (the wait in days).
Push i.

Days left on the stack at the end never see a warmer day, so their answer stays 0 (the array's default). Identical skeleton to Next Greater Element; the two changes are storing indices and computing i - popped instead of recording a value.

Logic Flowchart

graph TD
    A["answer all 0; stack empty"] --> B["for each day i"]
    B --> C{"stack nonempty AND temp[i] > temp[top]?"}
    C -->|Yes| D["j = pop(); answer[j] = i - j"]
    D --> C
    C -->|No| E["push i"]
    E --> F{"more?"}
    F -->|Yes| B
    F -->|No| G["leftover days stay 0"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows the index-based monotonic stack. While today is warmer than the temperature at the top index, that day's wait is resolved as today's index minus its index, so we pop and record it. Today's index is then pushed. Days still on the stack at the end keep a wait of zero.

Code

public static int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];                   // default 0
    Deque<Integer> stack = new ArrayDeque<>();   // indices, temps decreasing bottom-to-top
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int j = stack.pop();
            answer[j] = i - j;                   // days waited until warmer
        }
        stack.push(i);
    }
    return answer;
}

// Usage:
// dailyTemperatures([73,74,75,71,69,72,76,73]) -> [1,1,4,2,1,1,0,0]

This Java code keeps a decreasing stack of day indices. While today's temperature exceeds the temperature at the top index, that day's wait equals today's index minus its index, so it is popped and recorded. Today's index is pushed. Unresolved days keep a wait of zero.

Step-by-Step Walkthrough

A frame-by-frame trace on temperatures = [73,74,75,71,69,72,76,73] (key steps):

graph LR
    F0["i0(73),i1(74)>73: ans[0]=1<br/>i2(75)>74: ans[1]=1<br/>stack [2]"]
    F1["i3(71),i4(69) push<br/>[2,3,4]"]
    F2["i5(72)>69: ans[4]=1<br/>>71: ans[3]=2<br/>push 5 → [2,5]"]
    F3["i6(76)>72: ans[5]=1<br/>>75: ans[2]=4<br/>push 6 → [6]"]
    F4["i7(73) push [6,7]<br/>leftover 0: ans=[1,1,4,2,1,1,0,0]"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough processes the temperatures. Day one warms day zero after one day; day two warms day one. Days three and four cool and wait. Day five warms days four and three, after one and two days. Day six, the peak, warms days five and two, after one and four days. Days six and seven never warm, staying zero.

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

Interactive animation: The algorithm running step by step on the lesson's example, with the Java line that executes on each step.

Complexity

Time: O(n) - each index pushed and popped once. Space: O(n) - the stack.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Brute force	O(n²)	O(1)	Scan forward per day	Tiny inputs
Monotonic stack (indices)	O(n)	O(n)	Decreasing stack; record `i - j` on pop	Optimal

Same template as Next Greater Element, with the "distance" knob turned: store indices, compute i - poppedIndex. This is the archetype for every "how far until a greater/smaller element" question.

Interactive animation: Each index is pushed once and popped at most once - at most 2n comparisons, ever.

Variations & Follow-ups

Why store indices instead of temperatures?

The answer is a distance (i - j), which requires knowing positions. Storing temperatures alone would tell you what warms a day but not how many days away it is. This is the defining reason monotonic-stack problems store indices.

Why a decreasing stack again?

We're looking for the next greater value (a warmer day), so waiting days stack in decreasing temperature order; a warmer arrival resolves all the cooler tops. Same direction logic as Next Greater Element.

How would "days since a warmer day" (looking backward) change it?

Scan right-to-left instead, or compute previous-greater by keeping the same stack and reversing the traversal. The "previous greater/smaller" variants just flip the scan direction - another knob.

What about edge cases?

Strictly increasing ([30,40,50,60]): Each day warmed the very next day → all 1 except the last 0 (Example 2).
Strictly decreasing: No day ever warms → all 0.
Single day: Answer 0.
Plateau ([50,50,50]): Equal isn't warmer (> strict) → all 0.

Common Interview Pitfalls

Storing temperatures, not indices. You can't compute the day gap without positions.
Using >= instead of >. "Warmer" is strictly greater; equal temperatures don't resolve a wait.
Forgetting the default 0. Unresolved days must read 0 - initialize the answer array to zeros.
Wrong pop direction. Pop the smaller tops on a larger arrival (decreasing stack), not the reverse.

Why This Problem Matters

Daily Temperatures is the distance archetype - the realization that "next greater value" and "distance to next greater" are one algorithm differing only in what you record on a pop. Storing indices to compute spans is the exact mechanism that powers the hardest problems in this section (Largest Rectangle, Maximum Width Ramp), where the quantity of interest is a width measured between indices.

The next topic, Online Stock Span, adds a new dimension: it's a streaming/design problem. Prices arrive one at a time and you must answer, on each arrival, how many consecutive prior days had a price ≤ today's. The monotonic stack adapts beautifully by storing aggregated spans on each entry - a first taste of carrying summarized information up the stack rather than raw values.

Back to DSA Mastery - Interview Prep, End to End