LeetEye LeetEye
Medium Stack ~5 min

Daily Temperatures

stack 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. If there is no future day with warmer temperature, answer[i] = 0.

Examples

Example 1
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3
Input: temperatures = [30,60,90]
Output: [1,1,0]
Key Insight

Use a stack to track days waiting for a warmer day.

Next greater element = monotonic decreasing stack. Pop and resolve when current > stack top, then push current.

How to Approach This Problem

Pattern Recognition: When you see keywords like daily temperatures stack, think Stack.

Step-by-Step Reasoning

1 For each day i, scan forward to find the first warmer day. Time complexity?
Answer: O(n²)
For each of n days, we might scan up to n days forward.
2 The stack holds days that are:
Answer: Still waiting to find a warmer day
Days on the stack haven't found their next warmer day yet.
3 When processing day i with temperature T, pop from stack if:
Answer: Stack top's temperature < T
Day on stack top is cooler than today. Today is its "next warmer day"!
4 When popping day j because day i is warmer: answer[j] = ?
Answer: i - j
We want days to wait, not temperature difference. Days = index difference.
5 After resolving all cooler days, what do we do with the current day?
Answer: Push it onto the stack
Current day now waits for ITS next warmer day. It joins the stack.
6 The temperatures of days on the stack form a:
Answer: Decreasing sequence (from bottom to top)
We pop anything smaller than current before pushing. So bottom is largest, top is smallest of the waiting days. This is a monotonic decreasing stack.

Solution

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # Stack of indices
    
    for i in range(n):
        # Pop all days that found their warmer day
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_day = stack.pop()
            answer[prev_day] = i - prev_day
        
        # Current day waits for its warmer day
        stack.append(i)
    
    return answer

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Stack problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye