Leetcode - 739. Daily Temperatures

Medium

Dec 22, 2025

#stack

739. Daily Temperatures

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.

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]

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

Constraints:

Notes

Intuition: Store the temperature until a greater temperature is found.
Implementation: Initialize result with all zeros, we will add in values when we find the larger one. Use a stack to store both temp and index, iterate, while stack is not empty and stack top temp is less than curr, pop from stack, calculate distance with indices, add to result at popped index. Add curr temp and index to stack.
Complexity: Time O(n), Space O(n) (stack)

Solution

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n 
        # Space: O(n)
        stack = []
        # Time: O(n)
        for i in range(n):
            curr = temperatures[i]
            while stack and stack[-1][0] < curr:
                _, prev_i = stack.pop()
                result[prev_i] = i - prev_i
            stack.append((curr, i))
        return result
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()