Daily Temperatures Solution

Problem

Given a list of daily temperatures, determine how many days you must wait from each day until a strictly warmer day arrives. If no warmer day ever comes, the answer for that day is 0.

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Day 0 (73°) waits 1 day for day 1 (74°); day 2 (75°) waits 4 days for day 6 (76°); days 6 and 7 never see a warmer temperature so their answers stay 0.

Intuition

This is a "next greater element" problem — for each position, find the nearest future index whose value is strictly larger. Scanning forward from every element is O(n²). The shortcut is a monotonic stack: walk left-to-right and keep a stack of days still waiting for their warmer answer. The moment you see a temperature higher than the stack's top, that day's wait is over, so you pop and record the gap. Each element is pushed and popped at most once, giving O(n) overall.

Approach 1 — Brute Force

For each day, scan every future day in order until finding a strictly warmer temperature.

Allocate a result array of the same length, initialized to 0.
For each day i, iterate forward with j starting at i + 1.
When temperatures[j] > temperatures[i], record j - i in the result and break out of the inner loop.
If no warmer day is found, the result for day i remains 0.

1def dailyTemperatures(temperatures: list[int]) -> list[int]:
2    n = len(temperatures)
3    result = [0] * n
4    for i in range(n):
5        for j in range(i + 1, n):
6            if temperatures[j] > temperatures[i]:
7                result[i] = j - i
8                break
9    return result

Time: O(n²) — in the worst case (strictly descending array) every pair of days is compared.
Space: O(1) — no extra data structure beyond the output array.

Approach 2 — Monotonic Stack

Maintain a stack of indices for days that have not yet found a warmer day. Because we only push when the current temperature is not warmer than the top, the stack always holds a non-increasing sequence of temperatures.

Allocate a result array initialized to 0 and an empty stack.
For each index current_day, check whether temperatures[current_day] exceeds the temperature at pending_stack[-1].
While it does, pop the top index (colder_day) and record result[colder_day] = current_day - colder_day.
Push current_day — its warmer day has not arrived yet.
After the loop, any indices still on the stack never found a warmer day; their result is already 0.

1def dailyTemperatures(temperatures: list[int]) -> list[int]:
2    result = [0] * len(temperatures)
3    pending_stack = []  # indices of days still waiting for a warmer temperature
4
5    for current_day in range(len(temperatures)):
6        # resolve every colder day for which current_day is the answer
7        while pending_stack and temperatures[current_day] > temperatures[pending_stack[-1]]:
8            colder_day = pending_stack.pop()
9            result[colder_day] = current_day - colder_day
10        pending_stack.append(current_day)
11
12    return result

Time: O(n) — each index is pushed onto the stack once and popped at most once.
Space: O(n) — the stack holds at most n indices (a strictly decreasing temperature sequence pushes every index without popping).

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Input is tiny and the simpler loop is easier to debug
Monotonic Stack	O(n)	O(n)	Standard case — always prefer this for arrays of any meaningful size

Common Mistakes

Storing temperatures in the stack instead of indices — you need the index to compute the day gap; the temperature is just a comparison value that can be looked up afterward.
Off-by-one on the gap formula — the answer is current_day - colder_day. Day 6 minus day 2 equals 4, matching the expected output; subtracting an extra 1 produces the wrong answer.
Using >= instead of > — the problem requires a strictly warmer day; equal temperatures do not end the wait, so using >= incorrectly resolves ties.
Pushing before the while loop — if you push current_day first, the loop immediately compares the day against itself and can incorrectly record a wait of 0.
Trying to "clean up" the stack after the loop — indices still on the stack after the traversal are correct as-is (their result is 0 by initialization); iterating over them to assign 0 is redundant.

Daily Temperatures — Solution