Daily Temperatures
Problem Statement
Given an array of integers temperatures representing 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, set
answer[i] = 0.
Example:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Explanation:
- For day 1 (73°F), next warmer day is day 2 (74°F) → wait 1 day.
- For day 2 (74°F), next warmer day is day 3 (75°F) → wait 1 day.
- For day 3 (75°F), next warmer day is day 7 (76°F) → wait 4 days.
- For day 7 (76°F), no warmer day ahead → 0 days.
Approach 1: Brute Force
Idea: For each day, look ahead in the array until a warmer temperature is found.
Time Complexity: O(n²)
Space Complexity: O(1)
Initialize answer = [0] * n
for i in range(0, n):
for j in range(i+1, n):
if temperatures[j] > temperatures[i]:
answer[i] = j - i
break
💡 Think: This works but checks many unnecessary comparisons- inefficient for large inputs.
Approach 2: Monotonic Stack (Optimal)
Idea: Use a stack to keep track of indices of days with unresolved temperatures. When a warmer day is found, pop from stack and calculate waiting days.
Time Complexity: O(n)
Space Complexity: O(n)
Initialize stack = []
Initialize answer = [0] * n
for i in range(n):
while stack is not empty and temperatures[i] > temperatures[stack.top()]:
prev_day = stack.pop()
answer[prev_day] = i - prev_day
stack.push(i)
return answer
💡 Think: Stack maintains decreasing temperatures- whenever a higher one comes, resolve all smaller ones efficiently.