Daily Temperatures

Problem Description

Given an array of integers temperatures represents 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.

Examples

Constraints

• 1 <= temperatures.length <= 10⁵
• 30 <= temperatures[i] <= 100

Monotonic Decreasing Stack for Future Warmth

To solve this in O(n) time instead of O(n²) nested scanning, we maintain a monotonic decreasing stack. The stack holds the indices of days whose next warmer temperature hasn’t been found. We iterate through the array. For each day, while the stack is not empty and the current temperature is warmer than the temperature at the index stored at the top of the stack, we pop the index and compute the distance: days_to_wait = current_index - popped_index. We store this value in the result array. Then, we push the current index onto the stack.

Solution 1: Monotonic Stack

Keep day indices in a decreasing order stack to find the next larger element.

import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Stack<Integer> stack = new Stack<>(); // stores indices

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIdx = stack.pop();
                ans[prevIdx] = i - prevIdx;
            }
            stack.push(i);
        }
        return ans;
    }
}

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        ans = [0] * n
        stack = []  # stores indices
        
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                prev_idx = stack.pop()
                ans[prev_idx] = i - prev_idx
            stack.append(i)
            
        return ans

#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
        int n = temperatures.size();
        std::vector<int> ans(n, 0);
        std::stack<int> stack; // stores indices

        for (int i = 0; i < n; i++) {
            while (!stack.empty() && temperatures[i] > temperatures[stack.top()]) {
                int prevIdx = stack.top();
                stack.pop();
                ans[prevIdx] = i - prevIdx;
            }
            stack.push(i);
        }
        return ans;
    }
};

Complexity Analysis

• Time Complexity: O(n) because each index is pushed onto the stack exactly once and popped from the stack at most once.
• Space Complexity: O(n) auxiliary space to store indices in the stack in the worst case (e.g. temperatures in decreasing order).

Where It Breaks

If the input array contains an infinite streaming sequence, holding indices in memory is not feasible. In standard technical interview bounds, however, the O(n) memory allocation is acceptable.

Common Mistakes

• Storing values instead of indices: Storing raw temperatures in the stack instead of their index coordinates. The distance computation requires the indices.
• Incorrect comparison operator: Using >= instead of > when checking for warmer temperatures. The problem asks for a strictly warmer day, not an equal one.

Frequently Asked Questions

Why does this count as O(n) time? Although there is a nested while loop, the inner block can only execute at most once per element across the entire run. This results in an amortized time complexity of O(2n) = O(n).

What happens to elements that remain on the stack? Their values in the result array remain 0 (the default value), which is correct since no warmer temperature exists for them in the future.

← All Problems