Problem Statement

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 i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Additional information

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

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]

Brute Force

Intuition
For each day, we simply look forward to find the next day with a higher temperature. We compare the current day with every future day until we either find a warmer one or reach the end. If we find a warmer day, we record how many days it took. If not, the answer is 0. This method is easy to understand but slow because every day may scan many days ahead.

Algorithm

1. Let res store the number of days until a warmer temperature.
2. For each index i:

• Start checking from the next day j = i + 1.
• Count how many steps it takes to find a warmer day (temperatures[j] > temperatures[i]).
• If a warmer day is found, store the count.
• Otherwise, store 0.

3. Return the result array res.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    res = []

    for i in range(n):
        count = 1
        j = i + 1
        while j < n:
            if temperatures[j] > temperatures[i]:
                break
            j += 1
            count += 1
        
        count = 0 if j == n else count
        res.append(count)
        
    return res

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: In the worst case (a decreasing array like [99, 98, 97...]), for every element i, we scan all remaining n-1-i elements.

• Space complexity: O(1)

• Reason: We use constant extra space (excluding the output array).

Monotonic Stack (Optimal)

Intuition
We can process the temperatures and keep a "history" of days that haven't found a warmer day yet. A Monotonic Decreasing Stack is perfect for this.

We iterate through the list. If the current temperature is warmer than the temperature at the index stored at the top of the stack, it means the current day is the "warmer day" those previous days were waiting for. We pop those days from the stack and calculate the difference. If the current temperature is cooler, we just push the current day onto the stack and wait for a future warmer day.

Algorithm

1. Initialize n = len(temperatures) and answer array of size n with 0.
2. Initialize an empty stack (to store indices).
3. Iterate i through the array:

• While the stack is not empty AND temperatures[i] > temperatures[stack[-1]]:

• prev_index = stack.pop()

• answer[prev_index] = i - prev_index

• Push i onto the stack.

4. Return answer.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # Stores indices
    
    for i, temp in enumerate(temperatures):
        # While current temp is warmer than the temp at the top of the stack
        while stack and temp > temperatures[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index
        stack.append(i)
        
    return answer

Time & Space Complexity

• Time complexity: O(n)

• Reason: Each index is pushed onto the stack exactly once and popped at most once.

• Space complexity: O(n)

• Reason: The stack can grow to size n in the worst case (strictly decreasing temperatures).