Domain 2MediumMEDIUM

Daily Temperatures

Uses a monotonic decreasing stack to track indices of days waiting for warmer temperatures, achieving O(N) time complexity.

Domain: medium•Updated: 2026-08-31
#monotonic stack#stack#O(N)#O(N)

Problem Breakdown

We are given an array temperatures representing daily temperatures in degrees Celsius. For each day at index i, we need to find the number of days until a warmer temperature occurs (an element strictly greater than T[i]). If no such future day exists, the value should be 0.

Inputs:

  • A list of integers temperatures with length between 1 and 30,000.
  • Values range from 30 to 100 (though logic holds for any integer).

Outputs:

  • An array of the same length where each element corresponds to the wait time or 0.

Implicit Constraints & Edge Cases:

  • Empty Input: Not possible per constraints, but logically handled by loops not executing.
  • Strictly Decreasing Sequence: Every day waits forever; output is all zeros. The stack will fill up and never pop until end of loop (except implicitly via initialization).
  • Last Element: Always 0 because there are no future days to check.
  • Duplicates: If T[i] == T[j] where j>ij > i, it does not count as warmer; strictly greater is required.

Intuition

A naive brute-force approach would iterate through the array for every day, checking subsequent days until a higher temperature is found or the end of the list is reached. This results in an O(N2)O(N^2) time complexity. Given N=30,000N=30,000, this could lead to ≈9×108\approx 9 \times 10^8 operations, which risks Time Limit Exceeded (TLE) on platforms like LeetCode or production systems.

We need a more efficient way to track “pending” days that are waiting for a warmer temperature. This is the classic Next Greater Element problem pattern.

  • We can maintain a stack of indices representing days we haven’t found an answer for yet.
  • To optimize, this stack should store temperatures in decreasing order (monotonic). If today’s temperature is higher than what sits at the top of our stack, it means today is the warmer day for that index on the stack. We can resolve those pending queries immediately and pop them off.

Approach

  1. Initialize a result list result with zeros to handle cases where no warmer day exists (default value). Alternatively, we could append/pop into an array of size N initialized to 0s; I will use pre-allocated logic for clarity on indexing. Actually, initializing the stack and building results dynamically is cleaner in Python if we map indices back later or just initialize result with zeros. Let’s initialize result = [0] * len(T).
  2. Initialize an empty list called stack to store indices of days waiting for a warmer temperature. The temperatures at these indices will be implicitly decreasing (monotonic).
  3. Iterate through the input array using index i:
    • While the stack is not empty and the current day’s temperature (T[i]) is greater than the temperature at the index stored on top of the stack:
      • We found a warmer day for the pending request in the stack.
      • Pop the previous index from the stack (let’s call it prev_idx).
      • Calculate wait time: i - prev_idx.
      • Store this value in result[prev_idx].
    • Push current index i onto the stack, as we are now waiting for a future warmer day.
  4. Return the populated result list.

Complexity Analysis

  • Time Complexity: O(N)O(N). Each element is pushed onto the stack exactly once and popped at most once during the iteration. The while loop condition ensures amortized constant time per element overall.
  • Space Complexity: O(N)O(N) for the result array (which is required output). Additionally, we use an auxiliary stack which can grow up to size NN in worst-case scenarios (e.g., strictly decreasing temperatures), so total space complexity remains linear relative to input size.

Solution

def dailyTemperatures(temperatures):
    n = len(temperatures)
    result = [0] * n  # Initialize with zeros for days that never get warmer
    
    stack = []  # Stack stores indices of temperatures waiting for a warmer day
    
    for i, temp in enumerate(temperatures):
        # While current temperature is higher than the one at top of stack:
        while stack and temperatures[stack[-1]] < temp:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        
        # Push current index to wait for future warmer day
        stack.append(i)
        
    return result

# Example usage (commented out):
# print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])) 

Edge Cases Handled

  • Strictly Decreasing Temperatures: The while loop never executes. All indices are pushed to the stack and remain there until the end of iteration. Since we initialized result with zeros, all entries correctly return 0 without needing explicit checks after the loop.
  • Single Element Input: Loop runs once for index 0. Stack gets [0]. No pop occurs. Returns [0], which is correct as no future day exists.
  • All Increasing Temperatures: The while condition triggers immediately on every step (except potentially the first). Each popped element finds its answer in O(1)O(1), resulting in minimal stack depth and optimal performance matching brute force for this specific case but with better worst-case bounds overall.