Coding Interview PatternsDaily Temperatures
MediumStacks
Daily Temperatures
Explanation & Solution
Description
Given an array of integers temperatures represents the daily temperatures, return an array answer such that 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 for which this is possible, keep answer[i] == 0 instead.
Input:temperatures = [73,74,75,71,69,72,76,73]
0
73
1
74
2
75
3
71
4
69
5
72
6
76
7
73
Output:[1,1,4,2,1,1,0,0]
0
1
1
1
2
4
3
2
4
1
5
1
6
0
7
0
Constraints
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
Approach
Stacks pattern
1. Monotonic Decreasing Stack
- Maintain a stack of indices where temperatures are in decreasing order from bottom to top
- The stack represents days that haven't yet found a warmer future day
2. Process Each Day
- For each day
i: - While the stack is non-empty and
temperatures[i]is warmer than the temperature at the top of the stack: - Pop the index
prevIndex - Set
answer[prevIndex] = i - prevIndex(the number of days waited) - Push the current index
ionto the stack
3. Remaining Stack Elements
- Any indices left on the stack never found a warmer day
- Their answer values remain
0(the initial fill value)
Key Insight
- The monotonic stack ensures each element is pushed and popped at most once, giving O(n) time
- By storing indices (not values), we can compute the distance between days directly
- This is a classic "next greater element" pattern applied to temperatures
Visualization
Input:
[73, 74, 75, 71, 69, 72, 76, 73]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
15 steps