Skip to content
DSA Grind
All 26 sections

Daily Temperatures (LC 739)

ProblemMediumLeetCode 739Updated
On this page

Pattern: Monotonic Stack (next greater element, distance flavour)
Difficulty: Medium
Key Concept: Keep a stack of indices whose answer is still unknown, in decreasing temperature order. A warmer day resolves several of them at once.

Problem Statement

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 there is no future day with a warmer temperature, answer[i] = 0.

Input: int[] temperatures, 1 <= n <= 10^5, 30 <= temperatures[i] <= 100
Output: int[] answer of the same length

Example

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

1. Algorithm & Pseudocode

Brute force

for i from 0 to n-1:
    for j from i+1 to n-1:
        if temps[j] > temps[i]:
            answer[i] = j - i
            break
return answer

Optimal (monotonic decreasing stack)

stack = empty stack of INDICES
answer = new int[n]                  // default 0 = "never gets warmer"

for i from 0 to n-1:
    while stack not empty AND temps[stack.top] < temps[i]:
        prev = stack.pop()
        answer[prev] = i - prev      // i is the first warmer day for prev
    stack.push(i)

return answer                        // leftovers keep their default 0

2. Step-by-Step Analysis (Beginner-Friendly)

  1. Why the brute force is wasteful For a decreasing run like [100, 99, 98, 97], day 0’s inner loop scans the entire rest of the array and finds nothing. Then day 1 does almost the same scan. You are re-reading the same elements over and over. At n = 10^5 that’s ~5·10^9 comparisons — too slow.

  2. The observation that fixes it When you arrive at day i with temperature 76, that single value is the answer for every pending colder day you’ve seen — not just the previous one. So instead of each day searching forward, let each new day push its answer backwards to everyone waiting.

  3. Who is “waiting”? A day is waiting if you haven’t yet found anything warmer than it. Keep those days on a stack. Because you only keep days that are still unresolved, the temperatures on that stack are automatically decreasing from bottom to top — if a day were colder than the one below it, the one below would already have been resolved.

  4. Why store indices, not temperatures The question asks “how many days”, which is a distance. i - prev needs prev’s position. Store indices and read temps[index] whenever you need the value.

  5. Why it is O(n), not O(n²) The while loop is nested inside the for, which looks quadratic. But each index is pushed exactly once and popped at most once. Across the entire run, the while body executes at most n times total. Amortised, that’s O(1) work per day.

  6. What about days still on the stack at the end? They never found anything warmer. answer was initialised to all zeros, which is exactly the required output — no cleanup loop needed.

3. The Dry Run

Input: [73, 74, 75, 71, 69, 72, 76, 73]

i temp Pops (index → answer) Stack after (indices) answer so far
0 73 — [0] [0,0,0,0,0,0,0,0]
1 74 pop 0 → 1-0 = 1 [1] [1,0,0,0,0,0,0,0]
2 75 pop 1 → 2-1 = 1 [2] [1,1,0,0,0,0,0,0]
3 71 — (71 < 75) [2,3] [1,1,0,0,0,0,0,0]
4 69 — (69 < 71) [2,3,4] [1,1,0,0,0,0,0,0]
5 72 pop 4 → 5-4 = 1; pop 3 → 5-3 = 2; stop (72 < 75) [2,5] [1,1,0,2,1,0,0,0]
6 76 pop 5 → 6-5 = 1; pop 2 → 6-2 = 4 [6] [1,1,4,2,1,1,0,0]
7 73 — (73 < 76) [6,7] [1,1,4,2,1,1,0,0]

Leftover indices 6, 7 keep answer = 0. Final: [1,1,4,2,1,1,0,0] ✓

4. Java Solution

Brute Force

class Solution {
    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;                     // first warmer day only
                }
            }
        }
        return answer;
    }
}

Time O(n²) · Space O(1) extra

Optimal

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];                    // default 0 handles "no warmer day"
        Deque<Integer> stack = new ArrayDeque<>();    // indices, temps decreasing bottom→top

        for (int i = 0; i < n; i++) {
            // temperatures[i] is the first warmer day for every colder pending index
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int prev = stack.pop();
                answer[prev] = i - prev;
            }
            stack.push(i);
        }
        return answer;
    }
}

Time O(n) — each index pushed once, popped ≤ once · Space O(n) worst case (strictly decreasing input keeps everything on the stack)

Bonus: O(1) extra space, scanning right → left

class Solution {
    public int[] dailyTemperatures(int[] t) {
        int n = t.length, hottest = 0;
        int[] answer = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (t[i] >= hottest) { hottest = t[i]; continue; }   // no warmer day exists
            int days = 1;
            while (t[i + days] <= t[i]) days += answer[i + days]; // JUMP using known answers
            answer[i] = days;
        }
        return answer;
    }
}

Worth mentioning as a follow-up: it reuses already-computed answers to leapfrog. Still O(n) amortised, but O(1) auxiliary space.

5. The “Java vs. Others” Edge

  • ArrayDeque over java.util.Stack — Stack extends Vector, so every operation is synchronized and its iterator runs bottom-to-top (the opposite of stack order). The JDK’s own Stack javadoc points you at Deque. Saying this unprompted is a senior signal.
  • Guard order matters: !stack.isEmpty() && temperatures[stack.peek()] < .... ArrayDeque.peek() returns null when empty, and auto-unboxing null to int throws NPE. Java’s && short-circuits, so the empty check must be first.
  • new int[n] is zero-filled by the JVM — the language guarantees it. In C you’d need memset; here the default is already the correct “no warmer day” answer.
  • Boxing cost: Deque<Integer> boxes every index. Values 30–100 hit the Integer cache, but indices up to 10^5 do not. If asked to squeeze it, offer int[] stack = new int[n]; int top = -1; — same logic, zero allocation.

6. Complexity Summary

Approach Time Space Notes
Brute force O(n²) O(1) TLE at n = 10^5
Monotonic stack O(n) O(n) Each index pushed/popped once
Right-to-left jump O(n) O(1) Reuses answer[] to skip ahead
# Problem Same knob?
LC 496 Next Greater Element I next greater + HashMap indirection
LC 503 Next Greater Element II next greater, circular (2n loop)
LC 901 Online Stock Span previous greater, streaming
LC 84 Largest Rectangle in Histogram next/previous smaller