Daily Temperatures medium

Description

Given an array temperatures representing 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 no future day has a warmer temperature, set answer[i] = 0.

Examples

> Case 1:
    Input:  temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
    Output: [1, 1, 4, 2, 1, 1, 0, 0]
 
> Case 2:
    Input:  temperatures = [30, 40, 50, 60]
    Output: [1, 1, 1, 0]
 
> Case 3:
    Input:  temperatures = [30, 60, 90]
    Output: [1, 1, 0]

Constraints

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100
• Aim for O(n) — the brute force O(n²) will TLE on large inputs.

Intuition

This is the Next Greater Element problem in disguise. Instead of storing the next greater value, we store the distance to it (j - i).

The same monotonic-stack trick applies: keep indices on the stack in decreasing-temperature order. When today’s temperature beats whatever’s on top, that older day has just found its warmer day — record the distance, pop it, and repeat.

temps = [73, 74, 75, 71, 69, 72, 76, 73]

i=0  73    stack empty → push 0          stack=[0]
i=1  74    74>73 → pop 0, ans[0]=1-0=1
           push 1                         stack=[1]      ans=[1, _, _, _, _, _, _, _]
i=2  75    75>74 → pop 1, ans[1]=2-1=1
           push 2                         stack=[2]      ans=[1, 1, _, _, _, _, _, _]
i=3  71    71<75 → push 3                 stack=[2,3]
i=4  69    69<71 → push 4                 stack=[2,3,4]
i=5  72    72>69 → pop 4, ans[4]=5-4=1
           72>71 → pop 3, ans[3]=5-3=2
           72<75 → push 5                 stack=[2,5]    ans=[1, 1, _, 2, 1, _, _, _]
i=6  76    76>72 → pop 5, ans[5]=6-5=1
           76>75 → pop 2, ans[2]=6-2=4
           push 6                         stack=[6]      ans=[1, 1, 4, 2, 1, 1, _, _]
i=7  73    73<76 → push 7                 stack=[6,7]

End. Stack=[6,7] never found a warmer day → ans[6]=0, ans[7]=0.
Final: [1, 1, 4, 2, 1, 1, 0, 0] ✓

Code

#include <vector>
#include <stack>
using namespace std;
 
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> answer(n, 0);
    stack<int> st;  // indices, temperatures decreasing from bottom to top
 
    for (int i = 0; i < n; i++) {
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int j = st.top(); st.pop();
            answer[j] = i - j;
        }
        st.push(i);
    }
    return answer;
}

def daily_temperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # indices
 
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
 
    return answer

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

Explanation

• The stack stores indices, not temperatures — because we need the distance, we need to remember where each waiting day lives.
• The temperatures at the indices on the stack are always strictly decreasing from bottom to top. That’s the monotonic invariant.
• When a new temperature is hotter than the top, it answers all waiting days that are colder than it — pop them in a single while-loop, recording each distance.
• Anything left on the stack at the end never found a warmer day → answer stays 0.

Analysis

• Time: O(n) — each index pushed once, popped at most once.
• Space: O(n) — stack and answer array.