Daily Temperatures

Medium Problem 37 of 151 Java and Python

Problem

Given an array temperatures of daily temperatures, return an array answer where 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.

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 ≤ temperatures.length ≤ 10⁵
30 ≤ temperatures[i] ≤ 100

Explanation

Keep a stack of days that have not yet seen a warmer day. Their temperatures are in decreasing order from bottom to top.

When today is warmer than the day on top, today answers that day: pop it and record today - thatDay. Keep popping while today is warmer, then push today.

Approach 1 · Naive

Scan forward from each day

Time O(n²)
Space O(1) besides the output

For each day, look ahead until you find a warmer one.

For each i, scan j = i + 1 … for the first temperatures[j] > temperatures[i].
Store j - i, or 0 if none.

Java

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;
                }
            }
        }
        return answer;
    }
}

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    answer[i] = j - i
                    break
        return answer

Approach 2 · Optimal

Monotonic stack of indices

Time O(n)
Space O(n)

Push each day's index. Before pushing, pop every colder day on the stack and fill in its answer.

For each day i: while the stack is not empty and temperatures[top] < temperatures[i], pop top and set answer[top] = i - top.
Push i. Days left on the stack keep the answer 0.

Java

import java.util.*;

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

Python

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []
        for i, temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temp:
                day = stack.pop()
                answer[day] = i - day
            stack.append(i)
        return answer

Complexity compared

Approach	Time	Space
Naive Scan forward from each day	O(n²)	O(1) besides the output
Optimal Monotonic stack of indices	O(n)	O(n)

Key takeaways

Store indices on the stack when the answer is a distance.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem