🌡 Next warmer day

Imagine you are given an array of daily temperatures: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]. Your task is to return an array answer such that answer[i] is the number of days you have to wait after the $i^{th}$ day to get a warmer temperature. If there is no future day with a warmer temperature, keep it 0. Leetcode source

The brute force approach which is $O(n^2)$ solution require scanning right the temperatures array to find temperature which is greater than the temperature at $i^{th}$ index.

We can optimize this solution based on a Monotonic Stack algorithm .

🔧 Solution

For this problem, we will maintain a strictly decreasing stack of indices. As long as the next day is colder, we haven't found a "warmer day" yet. We just note down its index and wait. The moment we find a day that is warmer than the day at the top of our stack, a light bulb goes off! We calculate the day difference, log it in our results, and pop that cold day off our waiting list.

</> Python implementation

def daily_temperatures(temperatures: list[int]) -> list[int]:
    # Initialize the results list with zeros
    res = [0] * len(temperatures)
    stack = []  # Pairs of (index, temperature)

    for curr_idx, curr_temp in enumerate(temperatures):
        # Check if the current day is warmer than the day at the top of the stack
        while stack and curr_temp > stack[-1][1]:
            prev_idx, prev_temp = stack.pop()
            # Calculate how many days we waited
            res[prev_idx] = curr_idx - prev_idx
            
        # Keep track of the current day
        stack.append((curr_idx, curr_temp))
        
    return res