Daily Temperatures

mediumStack47 stepsJava · Python · C++

For each day, how many days until a warmer one? Keep a stack of day indices with decreasing temperatures. When a warmer day arrives, pop every cooler day: its answer is the distance to today.

▶ Watch the animated trace

Traced input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]. Original problem: neetcode.io/problems/daily-temperatures

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Each index is pushed and popped once.

Key idea

Store indices, not temperatures, so you can compute the distance.
Days on the stack are still waiting for a warmer day.
ans[j] = i - j when day i pops day j.
Days left on the stack at the end keep the default 0.

Common mistakes

Popping on >= instead of >: equal temperatures are not warmer.
Brute force O(n²) times out on 10⁵ days.

Solution

Java

int[] dailyTemperatures(int[] temps) {
    int[] ans = new int[temps.length];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < temps.length; i++) {
        while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
            int j = stack.pop();
            ans[j] = i - j;
        }
        stack.push(i);
    }
    return ans;
}

Python

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

C++

vector<int> dailyTemperatures(vector<int>& temps) {
    vector<int> ans(temps.size());
    stack<int> st;
    for (int i = 0; i < (int)temps.size(); i++) {
        while (!st.empty() && temps[st.top()] < temps[i]) {
            int j = st.top(); st.pop();
            ans[j] = i - j;
        }
        st.push(i);
    }
    return ans;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Strictly decreasing No day ever gets warmer.	`temperatures = [5, 4, 3]`	`[0, 0, 0]`
Strictly increasing Every day pops the previous one.	`temperatures = [30, 40, 50, 60]`	`[1, 1, 1, 0]`
Equal temperatures 70 doesn't pop 70; both wait for 71.	`temperatures = [70, 70, 71]`	`[2, 1, 0]`
Single day No future days.	`temperatures = [50]`	`[0]`