Daily Temperatures

Problem

A weather service needs to compute, for each day in a forecast, how many days a user must wait before seeing a warmer temperature. Scanning forward from every day is O(n^2) - too slow for a year of hourly readings. Given a list of daily temperatures, return a list where each entry is the number of days until a strictly warmer temperature, or 0 if no such day exists.

Input:  [73, 74, 75, 71, 69, 72, 76, 73]  → [1, 1, 4, 2, 1, 1, 0, 0]
Input:  [30, 40, 50, 60]                   → [1, 1, 1, 0]
Input:  [60, 50, 40, 30]                   → [0, 0, 0, 0]

Solution

Approach: Monotonic decreasing stack of indices.

Walk the array left to right, keeping a stack of indices whose days have not yet found a warmer future. The stack stays monotonic: temperatures at the stored indices decrease from bottom to top. For each new day index, while the stack is non-empty and temperatures[stack[-1]] < temperatures[index], the day on top has finally met a warmer day - pop it as waiting_index and record result[waiting_index] = index - waiting_index, the gap in days. Keep popping, because one warm day can resolve many waiting colder days at once. Then push index so it can wait for its own warmer day.

The insight is that each day only ever waits for the first warmer day to its right, and the stack holds exactly those still-waiting days in decreasing-temperature order. When a warmer day arrives it settles every shorter waiter beneath it in one sweep. Trace [73, 74, 75, 71, 69, 72]: 73 waits, 74 pops 73 (gap 1) then waits, 75 pops 74 (gap 1) then waits, 71 and 69 just stack on top of 75, then 72 pops 69 (gap 1) and 71 (gap 2) but not 75, leaving indices [2, 5] still waiting.

Edge cases: Equal temperatures use strict <, so a repeated value never counts as warmer and those days keep their default 0. Days never popped (the global tail, or a strictly decreasing run) retain the pre-initialized 0.

Complexity: O(n) time, O(n) space - each index is pushed once and popped at most once, so total stack work is linear; the stack and result array each hold up to n entries.