FAANG · LeetCode #739

Daily Temperatures — three-stage drill

1The ProblemMedium

Daily Temperatures

For each day, how many days until a warmer temperature.

Examples

[73,74,75,71,76]→ [1,1,2,1,0]

constraint0 if no warmer day follows.

2The PatternTIME O(n) · SPACE O(n)

Monotonic Stack

A stack kept sorted; each new value pops everything it resolves, so each element is pushed and popped once — O(n).

Problems using this pattern

3The SolutionRESULT → [1,1,2,1,0]

Step through it

stack holds indices of days still waiting — kept in decreasing temperature

Step 1 / 11

Python▎pop the days this one resolves

1def dailyTemperatures(temps):
2    ans = [0] * len(temps)
3    stack = []                       # indices, decreasing temps
4    for i, t in enumerate(temps):
5        while stack and t > temps[stack[-1]]:
6            j = stack.pop()
7            ans[j] = i - j
8        stack.append(i)
9    return ans

why it worksKeep a stack of indices whose answer is still unknown, with decreasing temperatures. When today is warmer than the day on top, that day's wait is resolved (i − its index) — pop it. Each day is pushed and popped at most once, so O(n) instead of O(n²).

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Daily Temperatures — three-stage drill