Approach Summary
Monotonic decreasing stack of indices. When current temp > stack top temp, pop and record the wait time.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Full Solution & Approach
For each day you want the next warmer day — the classic next-greater-element problem with distances instead of values. A monotonic decreasing stack of indices does it in one pass. Iterate through the array; while the stack is non-empty and the current temperature is warmer than the temperature at the index on top of the stack, the current day is the answer for that top index — pop it and record the difference. Then push the current index. The stack stays strictly decreasing in temperature from bottom to top, which guarantees that when a warmer day arrives it correctly resolves every index it can. Each index is pushed once and popped once, so the total work is linear. The monotonic-stack pattern — a stack that pops when the invariant breaks — is the same machinery behind largest-rectangle and next-greater-element, and recognizing it turns O(n²) "scan right for each element" into O(n).
Each index enters and leaves the stack exactly once — O(n) time. The stack holds up to n indices — O(n) space.
Solution Code
Solution
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = 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();
res[j] = i - j;
}
stack.push(i);
}
return res;
}vector<int> dailyTemperatures(const vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n, 0);
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && temperatures[i] > temperatures[stk.back()]) {
int j = stk.back();
stk.pop_back();
res[j] = i - j;
}
stk.push_back(i);
}
return res;
}def daily_temperatures(temperatures: list[int]) -> list[int]:
n = len(temperatures)
res = [0] * n
stack = []
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
j = stack.pop()
res[j] = i - j
stack.append(i)
return resfunction dailyTemperatures(temperatures) {
const res = new Array(temperatures.length).fill(0);
const stack = [];
for (let i = 0; i < temperatures.length; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const j = stack.pop();
res[j] = i - j;
}
stack.push(i);
}
return res;
}Edge Cases to Watch
- Monotonically decreasing temperatures — all answers are 0
- Monotonically increasing temperatures — every answer is 1
- The hottest day — always 0
- Equal temperatures — the strict comparison means equal days do not resolve each other
Master the Stack Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Stack pattern.
How to Recognize This Pattern
- Next greater element with distance
- Days until warmer
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)