Problem statement

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 for 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 <= 40
• 30 <= temperatures[i] <= 100

Hints for Daily Temperatures

1. Hint 1

   A monotonic stack of indices with decreasing temperatures.

2. Hint 2

   When a warmer day arrives, it resolves every colder index on the stack.

How to solve Daily Temperatures

The brute force asks, for each day, "how far to the next warmer one?" and rescans the future — O(n²). Turn it around: when a warm day arrives, it is the answer for every pending colder day at once. Keep the unanswered days on a stack and let each new day settle all the ones it beats.

Approach

1. Start with an answer array of zeros — a day that is never resolved keeps 0, which is exactly what the problem asks for.
2. Keep a stack of indices of days still waiting for a warmer one. Their temperatures decrease from the bottom of the stack to the top.
3. For each day i: while the stack is non-empty and the day on top is colder than day i, pop that index j and record answer[j] = i - j.
4. Push i. It is now the newest unanswered day, and it is colder than everything left below it, so the stack stays decreasing.

Why it works

Index j is popped by the first day after it that is warmer: any earlier warmer day would have popped it already, and days that are colder get pushed on top without disturbing it. So the i that pops j is genuinely the nearest warmer day, and i - j is the wait.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Push indices, not temperatures — the answer is a distance, so the position is what you need on pop.
• The inner while is a loop, not an if: one warm day can resolve a long run of colder days.
• Although there is a nested loop, the cost is linear — each index is pushed once and popped at most once.

Reference solution

Python

from typing import List

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    out = [0] * len(temperatures)
    st = []
    for i, t in enumerate(temperatures):
        while st and temperatures[st[-1]] < t:
            j = st.pop()
            out[j] = i - j
        st.append(i)
    return out

Java

public static int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] out = new int[n];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && temperatures[st.peek()] < temperatures[i]) {
            int j = st.pop();
            out[j] = i - j;
        }
        st.push(i);
    }
    return out;
}

C++

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> out(n, 0);
    vector<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && temperatures[st.back()] < temperatures[i]) {
            int j = st.back();
            st.pop_back();
            out[j] = i - j;
        }
        st.push_back(i);
    }
    return out;
}

JavaScript

var dailyTemperatures = function(temperatures) {
    const out = new Array(temperatures.length).fill(0);
    const st = [];
    for (let i = 0; i < temperatures.length; i++) {
        while (st.length > 0 && temperatures[st[st.length - 1]] < temperatures[i]) {
            const j = st.pop();
            out[j] = i - j;
        }
        st.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium