LeetCode 739: Daily Temperatures — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Stack | Array | Monotonic Stack

The Problem

Given an array of daily temperatures, return an array where each element represents how many days you have to wait until a warmer temperature. If there is no future day with a warmer temperature, return 0 for that day.

Approach

Use a monotonic decreasing stack to efficiently find the next warmer temperature for each day. Iterate through temperatures from right to left, maintaining a stack of indices where temperatures are in decreasing order, and calculate the distance to the next warmer day.

Time: O(n) · Space: O(n)

Code

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        result = [0] * len(temperatures)

        for i in range(len(temperatures) - 1, -1, -1):
            while stack and temperatures[i] >= temperatures[stack[-1]]:
                stack.pop()
            if stack:
                result[i] = stack[-1] - i
            stack.append(i)

        return result