Given an array of integers temperatures representing daily temperatures, return an array answer where answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day with a warmer temperature, set answer[i] to 0. Temperatures range from 30 to 100, and the array length can be up to 10^5.
Example
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Day 0 (73) waits 1 day for 74. Day 2 (75) waits 4 days for 76. Day 3 (71) waits 2 days for 72. Days 6 and 7 have no warmer future day, so they get 0.
Use a monotonic decreasing stack that stores indices. For each new temperature, while it's warmer than the temperature at the index on top of the stack, pop that index and record the difference (current index minus popped index) as the number of days to wait. This efficiently pairs each day with the next warmer day.
Why this works
A monotonic decreasing stack keeps track of days that haven’t found a warmer day yet. When a new warmer temperature comes along, it resolves all the cooler days sitting on the stack. Each index is pushed and popped at most once, so the total work is O(n) despite the nested loop.
Step by step
- Push each day’s index onto the stack — it represents a day still waiting for a warmer temperature.
- When a warmer day arrives — pop all indices from the stack whose temperatures are cooler than today’s.
- Record the wait — for each popped index, the answer is
current_index - popped_index. - Leftover indices stay 0 — any indices remaining on the stack never found a warmer day, so their answer stays 0 (the default).
Time: O(n)
Space: O(n)
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] result = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // stores indices of days waiting for a warmer day
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { // current day is warmer
int prev = stack.pop();
result[prev] = i - prev; // days between prev and the next warmer day
}
stack.push(i);
}
return result;
}
}
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> result(n, 0);
stack<int> st; // stores indices of days waiting for a warmer day
for (int i = 0; i < n; i++) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) { // current day is warmer
int prev = st.top();
st.pop();
result[prev] = i - prev; // days between prev and the next warmer day
}
st.push(i);
}
return result;
}
};
def dailyTemperatures(temperatures: list[int]) -> list[int]:
n = len(temperatures)
result = [0] * n
stack = [] # stores indices of days waiting for a warmer day
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]: # current day is warmer than top
prev = stack.pop()
result[prev] = i - prev # days between prev and the next warmer day
stack.append(i)
return result