Problem 9.5 · Stack and Monotonic StackMedium

Daily Temperatures

What it teaches: The monotonic stack with distances: each warmer day pops every cooler day waiting on the stack.

Practise it on judges as “Daily Temperatures”.

The problem

Given daily temperatures, return an array where answer[i] is the number of days after day i until a warmer temperature. Use 0 if there is no warmer day.

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, 60, 90]
Output: [1, 1, 0]

Constraints

1 ≤ n ≤ 10⁵
30 ≤ temperature ≤ 100

Pattern clues in the wording

→ "Next greater" for every position
→ Answer is a distance in indexes

These clues point to Monotonic Stack: Keep a stack whose values only increase (or decrease); each element pops everything it beats, finding "next greater/smaller" in one pass.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        return new int[temperatures.length];
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	temperatures = [73,74,75,71,69,72,76,73]	[1,1,4,2,1,1,0,0]
2	temperatures = [30,60,90]	[1,1,0]

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Brute force: scan ahead · O(n²)2. Optimal: monotonic stack of waiting days · O(n)

Brute force: scan ahead

Time O(n²) Space O(1)

For each day, look ahead until a warmer day.

Approach 1

class Solution {
    public int[] dailyTemperatures(int[] t) {
        int[] ans = new int[t.length];
        for (int i = 0; i < t.length; i++)
            for (int j = i + 1; j < t.length; j++)
                if (t[j] > t[i]) { ans[i] = j - i; break; }
        return ans;
    }
}

Verdict: Too slow for 10⁵ days on falling temperatures.

Optimal: monotonic stack of waiting days

Time O(n) Space O(n)

Keep indexes of days without an answer yet, with temperatures decreasing upwards. Day i pops every colder day d and sets ans[d] = i − d, then waits itself.

▶ Dry run: Waiting for warmer daystemperatures = [73, 74, 75, 71, 69, 72, 76]

↑i

waiting(stack)

2 (75)

answer(list)

1100000

Step 1/474 answered 73 (1 day), 75 answered 74 (1 day). 75 waits.

Approach 2

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] dailyTemperatures(int[] t) {
        int[] ans = new int[t.length];
        Deque<Integer> waiting = new ArrayDeque<>();
        for (int i = 0; i < t.length; i++) {
            while (!waiting.isEmpty() && t[i] > t[waiting.peek()]) {
                int d = waiting.pop();
                ans[d] = i - d;
            }
            waiting.push(i);
        }
        return ans;
    }
}

Verdict: Each day is pushed and popped once.

Before you submit

Edge cases and common mistakes

Test these inputs

Strictly decreasing (all 0)
Strictly increasing (all 1 except the last)
Equal temperatures (not warmer)

Mistakes people make

Popping on equal temperatures (>=), which gives wrong answers for ties.
Storing temperatures instead of indexes.

Interview

Follow-up questions

Can you do it with O(1) extra space?

Command Palette