Daily Temperatures
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber
Problem
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Brute force checks every future day for each day — O(n²). The monotonic stack approach brings it to O(n).
Use a monotonic decreasing stack storing indices (not values). The stack holds days that haven't found a warmer day yet.
When you encounter a warmer day, pop all cooler days from the stack and record the distance. Each index is pushed and popped at most once.
Why it works: the stack maintains days in decreasing temperature order. A warmer day "resolves" all previous cooler days.
Visual walkthrough for [73,74,75,71,69,72,76,73]:
i=0: stack=[0(73)]
i=1: 74>73, pop 0, result[0]=1-0=1. stack=[1(74)]
i=2: 75>74, pop 1, result[1]=2-1=1. stack=[2(75)]
i=3: 71<75, push. stack=[2(75),3(71)]
i=4: 69<71, push. stack=[2(75),3(71),4(69)]
i=5: 72>69, pop 4, result[4]=5-4=1. 72>71, pop 3, result[3]=5-3=2. 72<75, push. stack=[2(75),5(72)]
i=6: 76>72, pop 5, result[5]=6-5=1. 76>75, pop 2, result[2]=6-2=4. stack=[6(76)]
i=7: 73<76, push. stack=[6(76),7(73)]
Remaining in stack get 0. Result: [1,1,4,2,1,1,0,0]
Edge cases: all same temperature (all zeros), strictly increasing (all ones), strictly decreasing (all zeros except last).
Optimal Approach
Step 1: Create result array of size n, fill with 0.
Step 2: Use a stack to store indices.
Step 3: For each day i:
While stack is not empty and temperatures[i] > temperatures[stack[-1]]:
j = stack.pop()
result[j] = i - j
Push i onto stack.
Step 4: Remaining indices in stack already have result[j] = 0.
Each index is pushed once and popped once, giving O(n) time.
Time: O(n). Space: O(n).
What Trips People Up in Real Interviews
Using brute force O(n²). The monotonic stack approach is O(n) and is what the interviewer expects.
Storing values in the stack instead of indices. You need indices to compute the answer (difference in positions).
Not handling the case where no warmer day exists. The answer for that day is 0 (already initialized).
Forgetting that the stack might not be empty after the loop. Remaining indices already have result = 0.
Using a monotonic INCREASING stack instead of decreasing. You need a decreasing stack so that when you find a warmer day, it resolves all previous cooler days. An increasing stack never pops.
Solution Code
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = []
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
j = stack.pop()
result[j] = i - j
stack.append(i)
return resultFrequently Asked Questions
What is the Daily Temperatures problem?
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.
How do you solve Daily Temperatures?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Daily Temperatures?
Daily Temperatures is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a medium difficulty problem.
What are common mistakes on Daily Temperatures?
- Using brute force `O(n²)`. The monotonic stack approach is `O(n)` and is what the interviewer expects.
- Storing values in the stack instead of indices. You need indices to compute the answer (difference in positions).
- Not handling the case where no warmer day exists. The answer for that day is 0 (already initialized).
- Forgetting that the stack might not be empty after the loop. Remaining indices already have `result = 0`.
- Using a monotonic INCREASING stack instead of decreasing. You need a decreasing stack so that when you find a warmer day, it resolves all previous cooler days. An increasing stack never pops.