739. Daily Temperatures

739

MediumMonotonic Stack and Monotonic QueueMonotonic decreasing stackNext greater element

Daily Temperatures

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

Open official problem prompt ↗

In plain English

For every day, measure the distance to the first later day that is strictly warmer, in a single pass instead of comparing every pair.

Picture it like this

Imagine people standing in a line each holding a thermometer, waiting for someone taller behind them. Each person waits until a taller person walks up; the moment that happens they leave the queue and note how long they waited.

Example

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Why: Day 0 (73) sees 74 the next day (wait 1); day 2 (75) must wait until day 6 (76), which is 4 days.

Constraints

1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100

Pattern lesson

See the pattern, then code

Next greater element

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. Keep a stack of indices whose warmer day has not been found yet, ordered by decreasing temperature. When a hotter day arrives it resolves every colder day sitting on top of the stack at once, and the gap in indices is the wait.

New words, made simpleKnow these before the algorithm

Monotonic stack: A stack whose values stay sorted (here strictly decreasing) so the next larger value can be found in amortized O(1).
Amortized O(1): Each index is pushed once and popped at most once, so the total work across all pops is O(n).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force scan

Quadratic time times out on arrays up to 10^5.

For each day, scan forward until a warmer temperature is found.

Time O(n^2)Space O(1)

Best choiceMonotonic decreasing stack

Every index is pushed and popped once, giving linear time.

Maintain a stack of unresolved indices; a hotter day pops and resolves all colder ones beneath it.

Time O(n)Space O(n)

The rule we keep true

Invariant

The temperatures at the indices held on the stack are strictly decreasing from bottom to top, meaning none of them has yet met a warmer day.

Why this is correct

Reasoning

An index stays on the stack exactly until the first later day warmer than it appears. Because the stack is decreasing, that day is warmer than everything above the resolved index too, so we resolve each pending day with the earliest possible warmer day, and the index difference is the correct wait.

The algorithm in three movesSay these aloud before coding

1Initialize answer with zeros and an empty stack of indices

stack (indices) = [2, 5] both awaiting a warmer day

2For each day, while the stack's top is colder than today, pop it and record the index gap as its wait

day 6 temp 76 pops idx 5 (wait 1) then idx 2 (wait 4)

3Push today's index onto the stack

answer[2] = 6 - 2 = 4

4Indices never resolved keep their default 0

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

730

741

752

713

694

725

766

737

1 · Read75

2 · AskIs 75 warmer than the stack top (74)?

3 · Update statestack = [2] (after popping 0,1)

4 · ResultPush index 2; still waiting.

Key takeaway

Day 6 (76) resolves the pending colder days 71/69/72 and the earlier 75 at index 2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Set up output and stack
answer defaults to 0 so unresolved days need no extra handling; the stack holds indices, not temperatures, so we can compute the gap.
2
Lines 6-9Resolve colder days
Any stacked day colder than today has just found its warmer day; record i - j and pop it.
3
Lines 10Push today
Today itself is now the newest unresolved day awaiting something warmer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Strictly decreasing temperatures leave every answer at 0
The last day is always 0
Equal temperatures do NOT count as warmer, so use strict less-than when popping

Common beginner mistakes

Using <= instead of < when comparing, which wrongly treats an equal temperature as warmer
Storing temperatures instead of indices, losing the ability to compute the day gap
Forgetting that leftover stack indices should stay 0 rather than being overwritten

Check your understanding

Why is the total work O(n) even though there is a while loop inside the for loop?

Daily Temperatures

Daily Temperatures

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue