Problem Overview
LeetCode 739 — Daily Temperatures — gives you an integer array temperatures where temperatures[i] is the temperature on day i. You must return an array answer where answer[i] is the number of days you have to wait after day i until a warmer temperature. If there is no future day with a higher temperature, answer[i] = 0. The answer array is the same length as the input.
For example, given temperatures = [73, 74, 75, 71, 69, 72, 76, 73], the output is [1, 1, 4, 2, 1, 1, 0, 0]. Day 0 has temperature 73 and the next warmer day is day 1 with temperature 74, so answer[0] = 1. Day 2 has temperature 75 and must wait until day 6 with temperature 76, so answer[2] = 4. Days 6 and 7 have no future warmer day so their answers are 0.
LeetCode 739 is rated Medium and is a canonical introduction to the monotonic stack pattern. The brute force O(n^2) approach is easy to write but fails on large inputs. The optimal solution uses a monotonic decreasing stack of indices to achieve O(n) time and O(n) space, processing each element at most twice — once when pushed, once when popped.
- 1 <= temperatures.length <= 100,000
- 30 <= temperatures[i] <= 100
- answer[i] = number of days to wait for a warmer day; 0 if none exists
- The answer array must be returned — in-place modification is acceptable
- Each element is processed at most twice in the optimal solution (one push, one pop)
Brute Force
The brute force approach uses two nested loops. The outer loop iterates over each day i. The inner loop scans forward from i+1, checking each future day j until it finds a day where temperatures[j] > temperatures[i]. When found, answer[i] = j - i. If the inner loop exhausts all remaining days without finding a warmer temperature, answer[i] remains 0.
This approach is correct and easy to reason about. However, its time complexity is O(n^2) in the worst case. A strictly decreasing temperature sequence forces the inner loop to scan all remaining days for each day i — for n = 100,000 that is up to 5 billion operations, which will time out on LeetCode. The space complexity is O(1) beyond the output array.
The worst-case input for brute force is a strictly decreasing sequence like [100, 99, 98, ..., 31, 30]. Every day must scan all subsequent days before concluding there is no warmer future day. The brute force serves as a correctness reference but must be replaced by the monotonic stack approach for any input of meaningful size.
The monotonic stack processes each element at most twice — O(n) total regardless of input pattern
In the brute force, a decreasing sequence causes O(n^2) comparisons because every day scans forward past all remaining days. The monotonic stack eliminates this by deferring resolution: instead of scanning forward eagerly, it pushes each unresolved day onto the stack and resolves it in O(1) when the next warmer day is encountered. Each element is pushed once and popped at most once, so the total work across the entire array is O(n) — not O(n) per element, but O(n) total.
Monotonic Stack Intuition
The key insight is that days are resolved out of order — day i might not learn its answer until many days later when the next warmer day finally arrives. A stack is the right data structure for this because it naturally handles last-in first-out resolution: the most recently pushed unresolved day will typically be resolved before older ones.
We maintain a stack of indices. The invariant is that the temperatures at those indices form a strictly decreasing sequence from bottom to top of the stack — a monotonic decreasing stack. Each element on the stack represents a day that is still waiting for a warmer day. When we encounter a day whose temperature is higher than the top of the stack, we know the stack top has found its answer.
We pop the stack top, compute the wait time as current_index - popped_index, and store it in the answer array. We keep popping as long as the current temperature exceeds the temperature at the stack top. Once the stack is empty or the top is not cooler than the current day, we push the current index and move on. Days with no warmer future day simply remain on the stack; they keep their default answer of 0.
How the Stack Works
The algorithm iterates through every index i from left to right. Before pushing i, we check if the stack is non-empty and if temperatures[stack.top()] < temperatures[i]. If so, the current day is warmer than the day stored at the stack top. We pop the top index (call it top_idx), compute answer[top_idx] = i - top_idx, and repeat the check with the new stack top.
We continue this pop-and-resolve loop as long as the stack is non-empty and the current temperature exceeds the temperature at the new stack top. When the loop exits — either the stack is empty or the top is not cooler — we push i onto the stack. The stack always maintains the invariant that temperatures at stored indices decrease from bottom to top.
After the outer loop completes, any indices remaining on the stack have no future warmer day. Their answer values remain 0, which is the default since we initialize the answer array to all zeros. There is no cleanup step needed — the remaining stack elements are simply ignored.
The stack is monotonic decreasing — each element on it is waiting for a warmer day and the first warmer day resolves them all in one sweep
Because the stack maintains a decreasing temperature invariant, a single warmer day can resolve multiple waiting days in one pass through the while loop. For example, if the stack holds indices for temperatures [75, 71, 69] and the current day is 76 degrees, all three are resolved in sequence: 69 is resolved first (top of stack), then 71, then 75 — each in O(1). This batch resolution is what gives the monotonic stack its O(n) amortized efficiency even when a single element triggers many pops.
Walk-Through Example
Trace temperatures = [73, 74, 75, 71, 69, 72, 76, 73] step by step. The answer array starts as [0, 0, 0, 0, 0, 0, 0, 0] and the stack starts empty. At each step we show the current index and temperature, the stack state before and after, and any answer updates.
i=0 (73): stack empty, push 0. Stack: [0]. i=1 (74): temperatures[0]=73 < 74, pop 0, answer[0]=1-0=1. Stack empty, push 1. Stack: [1]. i=2 (75): temperatures[1]=74 < 75, pop 1, answer[1]=2-1=1. Stack empty, push 2. Stack: [2]. i=3 (71): 75 > 71, just push 3. Stack: [2, 3]. i=4 (69): 71 > 69, just push 4. Stack: [2, 3, 4].
i=5 (72): temperatures[4]=69 < 72, pop 4, answer[4]=5-4=1. temperatures[3]=71 < 72, pop 3, answer[3]=5-3=2. temperatures[2]=75 > 72, stop. Push 5. Stack: [2, 5]. i=6 (76): temperatures[5]=72 < 76, pop 5, answer[5]=6-5=1. temperatures[2]=75 < 76, pop 2, answer[2]=6-2=4. Stack empty, push 6. Stack: [6]. i=7 (73): 76 > 73, just push 7. Stack: [6, 7]. Final answer: [1, 1, 4, 2, 1, 1, 0, 0].
- 1i=0 (73): push 0 → stack: [0]
- 2i=1 (74): pop 0, answer[0]=1 → stack: [], push 1 → stack: [1]
- 3i=2 (75): pop 1, answer[1]=1 → stack: [], push 2 → stack: [2]
- 4i=3 (71): 75>71, push 3 → stack: [2,3]
- 5i=4 (69): 71>69, push 4 → stack: [2,3,4]
- 6i=5 (72): pop 4→answer[4]=1, pop 3→answer[3]=2, 75>72 stop, push 5 → stack: [2,5]
- 7i=6 (76): pop 5→answer[5]=1, pop 2→answer[2]=4, empty, push 6 → stack: [6]
- 8i=7 (73): 76>73, push 7 → stack: [6,7]
- 9Remaining [6,7] on stack → answer[6]=0, answer[7]=0 (already default)
- 10Result: [1, 1, 4, 2, 1, 1, 0, 0]
Code Walkthrough Python and Java
Python solution (12 lines): def dailyTemperatures(temperatures): n = len(temperatures); answer = [0] * n; stack = []; for i in range(n): while stack and temperatures[stack[-1]] < temperatures[i]: top = stack.pop(); answer[top] = i - top; stack.append(i); return answer. The result array is initialized to all zeros so days that never find a warmer temperature require no special handling. The while loop pops and resolves all cooler days before pushing the current index.
Java solution: 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[stack.peek()] < temperatures[i]) { int top = stack.pop(); answer[top] = i - top; } stack.push(i); } return answer; }. Java uses ArrayDeque as a stack. Note that Deque.push() adds to the front and peek()/pop() access the front — equivalent to stack behavior. Time is O(n), space is O(n) for both the stack and the answer array.
Both implementations share the same core structure: initialize answer to zeros, iterate with a single for loop, pop cooler indices while resolving their answers, then push the current index. The answer array initialized to 0 is what handles the no-warmer-future-day case automatically — remaining stack elements are simply never popped and their zero default is correct.
Store indices not temperatures on the stack — you need the index to compute the day difference
A common mistake is pushing temperatures onto the stack instead of indices. When you pop a temperature, you know a warmer day was found, but you cannot compute the wait time because you need the original index of the popped day. By storing indices instead, you can both look up the temperature via temperatures[index] for the comparison and compute the wait time as current_index - popped_index. Always push indices, never temperatures.