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 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,70]
Output: [1,1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Constraints:

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

Solution

Approach: Monotonic Decreasing Stack

The key insight is to use a stack to keep track of indices of days with temperatures we haven’t found a warmer day for yet. We maintain the stack in decreasing order of temperatures.

For each day:

While the current temperature is warmer than temperatures at indices in the stack, we’ve found their answer
Pop those indices and calculate the number of days
Push the current index onto the stack

Implementation

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []  # Stack stores indices

        for i in range(n):
            # While current temp is warmer than temps at stack indices
            while stack and temperatures[i] > temperatures[stack[-1]]:
                prev_index = stack.pop()
                answer[prev_index] = i - prev_index

            stack.append(i)

        # Remaining indices in stack have no warmer day (already 0)
        return answer

Alternative (Iterating Backwards):

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

        for i in range(n - 1, -1, -1):
            # Pop indices with lower or equal temperatures
            while stack and temperatures[i] >= temperatures[stack[-1]]:
                stack.pop()

            # If stack not empty, next warmer day is at stack[-1]
            if stack:
                answer[i] = stack[-1] - i

            stack.append(i)

        return answer

Complexity Analysis

Time Complexity: O(n), where n is the length of the temperatures array. Each index is pushed and popped from the stack at most once.
Space Complexity: O(n) in the worst case, when temperatures are in decreasing order and we push all indices onto the stack.

Key Insights

Monotonic Stack Pattern: We maintain a stack of indices where temperatures are in decreasing order. This allows us to quickly find the next warmer day.
Stack Stores Indices: We store indices (not temperatures) because we need to calculate the difference in days. We can access temperatures using these indices.
Greedy Popping: When we find a warmer day, we can immediately answer for all previous days that are cooler. We pop them all from the stack.
No Warmer Day: Indices remaining in the stack after processing all days have no warmer day ahead, so their answer stays 0.
Forward vs Backward: Both approaches work. Forward iteration is more intuitive (we find warmer days as we go), but backward iteration can also solve it by building the answer in reverse.