TL;DR
Monotonic decreasing stack of unanswered indices, one pass — O(n) time, O(n) space (an O(1)-extra-space backward-jump variant exists).
Approach 1 — Brute force
For each day, scan forward until you find a strictly warmer day.
def dailyTemperatures(temperatures: list[int]) -> list[int]:
n = len(temperatures)
answer = [0] * n
for i in range(n):
for j in range(i + 1, n):
if temperatures[j] > temperatures[i]:
answer[i] = j - i
break
return answer
Complexity: O(n^2) time, O(1) extra space.
Why the constraints rule it out: a long non-increasing input (e.g. 10^5 days of slowly falling temperatures) makes every inner scan run to the end — about 5·10^9 comparisons, past any time limit.
Approach 2 — Monotonic decreasing stack
The insight: instead of each day searching forward for its answer, let each new day answer the earlier days waiting on it. Keep a stack of indices still waiting; their temperatures are strictly decreasing from bottom to top, because any day warmer than the one below it would already have been answered. This is a monotonic stack: it stays sorted by popping every element the new value exceeds. When day j arrives, it pops and answers every waiting day colder than it, then pushes itself.
def dailyTemperatures(temperatures: list[int]) -> list[int]:
answer = [0] * len(temperatures)
stack: list[int] = [] # indices, temps decreasing
for j, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
i = stack.pop()
answer[i] = j - i # day j answers day i
stack.append(j)
return answer # leftovers keep 0
Walkthrough on [73, 74, 75, 71, 69, 72, 76, 73]:
| j | temp | pops (index: answer) | stack after (indices) |
|---|
| 0 | 73 | — | 0 |
| 1 | 74 | 0 → 1 | 1 |
| 2 | 75 | 1 → 1 | 2 |
| 3 | 71 | — | 2 3 |
| 4 | 69 | — | 2 3 4 |
| 5 | 72 | 4 → 1, 3 → 2 | 2 5 |
| 6 | 76 | 5 → 1, 2 → 4 | 6 |
| 7 | 73 | — | 6 7 |
Indices 6 and 7 stay unanswered → 0. Result: [1, 1, 4, 2, 1, 1, 0, 0].
Complexity: O(n) time — every index is pushed once and popped at most once, so the while is amortized O(1). O(n) space for the stack.
Approach 3 — Backward pass with answer-array jumps
The insight: working right to left, day i’s warmer day lies at or beyond i + 1. If day j isn’t warm enough, nothing between j and j + answer[j] can be either (all are <= temperatures[j]), so hop straight to j + answer[j]. The already-filled answer array serves as a jump table, removing the need for a stack.
def dailyTemperatures(temperatures: list[int]) -> list[int]:
n = len(temperatures)
answer = [0] * n
for i in range(n - 2, -1, -1):
j = i + 1
while j < n and temperatures[j] <= temperatures[i]:
if answer[j] == 0:
j = n # nothing warmer ever appears
else:
j += answer[j] # leapfrog day j's whole cold run
if j < n:
answer[i] = j - i
return answer
Walkthrough (same example), filling right to left: day 5 (72) checks day 6 (76 > 72) → 1. Day 3 (71) checks day 4 (69 ≤ 71), hops by answer[4] = 1 to day 5 (72 > 71) → 2. Day 2 (75) checks day 3, hops +2 to day 5, hops +1 to day 6 (76 > 75) → 4. Final array matches: [1, 1, 4, 2, 1, 1, 0, 0].
Complexity: O(n) time amortized (each hop skips a run that is never re-examined at that level), O(1) extra space beyond the output.
Common pitfalls
- Storing temperatures on the stack instead of indices — you need
j - i to compute the wait, so the stack must hold indices.
< vs <= in the pop condition: “strictly warmer” means pop on temperatures[top] < temp; popping equal temperatures gives wrong answers for repeats like [73, 73, 74].- Forgetting the leftovers: indices remaining on the stack correctly keep answer 0 only because the array was initialized to 0 — don’t “finalize” them with anything else.
- In the jump variant, failing to treat
answer[j] == 0 as “give up” causes an infinite loop on plateaus.
Pattern takeaway
“Next greater element” questions are the canonical monotonic-stack pattern: keep a stack of unresolved indices in decreasing value order, and let each new element resolve everything it beats before being pushed. Whenever a problem asks, for each position, about the nearest later (or earlier) element passing a comparison, expect an O(n) monotonic-stack pass instead of the O(n^2) rescan.