Daily Temperatures

Given a list of daily temperatures, return an array where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If there is no future day, put 0.

Why this is worth learning

The stack holds unresolved days, not temperatures alone. A new warmer day resolves exactly the colder unresolved suffix, with the first such day being the nearest answer.

Before coding: one-minute experiment

For [70,70,71], what are the waiting times?

Function signature

func DailyTemperatures(temperatures []int) []int

Inputs / outputs

• temperatures: slice of integers.
• Return: slice of wait times.

Example

temperatures = [73,74,75,71,69,72,76,73]
Output = [1,1,4,2,1,1,0,0]

Constraints

• 1 <= len(temperatures) <= 100_000
• -100 <= temperatures[i] <= 200

Core idea (near-solution)

Use a monotonic decreasing stack of indices. When a new temperature is higher than the top, you have found the next warmer day for that index.

Invariant: indices increase from bottom to top, while their temperatures are non-increasing. Equal temperatures remain on the stack because neither is strictly warmer than the other.

Algorithm (step-by-step)

1. Initialize an output array with zeros.
2. Initialize an empty stack of indices.
3. For each index i:
   • While stack not empty and temperatures[i] > temperatures[stackTop]:
     • Pop j and set answer[j] = i - j.
   • Push i onto the stack.
4. Return answer.

Correctness sketch

Indices on the stack are increasing and their temperatures are non-increasing. Every stacked day has seen no warmer day in the processed suffix. If the current temperature is strictly warmer than the top day, it is the first warmer day for that index, so their index difference is final. Pop and repeat for any earlier colder unresolved days. Remaining days are at least as warm as the current one and remain unresolved. Pushing the current index preserves both orders. At termination, unresolved days have no warmer future day and keep zero. Each index is pushed and popped at most once.

Trace (hand walkthrough)

Example input:
temperatures = [73,74,75,71,69,72,76,73]
Output = [1,1,4,2,1,1,0,0]

Walk:
- i=0 (73) push[0]; i=1 (74) >73 -> ans[0]=1, push[1]
- i=2 (75) >74 -> ans[1]=1, push[2]
- i=3 (71) push[3]; i=4 (69) push[4]
- i=5 (72) >69 -> ans[4]=1; >71 -> ans[3]=2; push[5]
- i=6 (76) >72 -> ans[5]=1; >75 -> ans[2]=4; push[6]

Pitfalls to avoid

• Storing temperatures instead of indices (you need distance).
• Popping on >= instead of >: an equal temperature does not resolve a strictly-warmer query.

Debugging lens

Use equal plateaus, strictly descending temperatures, and one final warm spike. Storing temperatures without indices loses the distance needed for the answer.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• Use a stack of indices with decreasing temperatures.
• When current temp is higher, pop and compute distances.

Reconstruction checkpoint

For [70,70,71], what are the waiting times?

Return to Stack + Monotonic · Module quiz