Loading…

mediumStack QueueLC #739Frequently asked

Daily Temperatures

Q: How do you solve Daily Temperatures using the Brute Force — Scan Forward (Baseline) approach?

When to use it: Mention to anchor the O(n²) cost, then improve with the monotonic stack the constraints demand. For every day `i`, walk forward until a strictly warmer day `j` is found and store `j − i`; if none, leave `0`. **Why mention it.** It directly encodes the definition and confirms the answer format. **Why it's too slow.** With `n` up to `10⁵`, the nested forward scan is `O(n²) ≈ 10¹⁰`. The wasted work is re-scanning the same future days for many starting points — exactly what a stack of pending days eliminates. Time complexity: O(n²). Space complexity: O(1).

LCPractice

Stack & Queue · 5 of 17 · 9 min

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

In plain English

For each day we want the distance to the next strictly warmer day. The brute force scans forward for every day (O(n²)). The key observation: when a warm day arrives, it resolves all colder days still waiting — so we keep those waiting days on a stack and settle them in bulk, touching each day a constant number of times.

Examples

Example 1

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Note: Day 0 (73) waits 1 day for 74; day 2 (75) waits 4 days for 76; days 6 and 7 have no warmer future day → 0.

Example 2

Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]
Note: Strictly increasing — each day's next day is warmer; the last has none.

Example 3

Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]
Note: Each warmer day immediately follows; the peak waits forever → 0.

Constraints

1 ≤ temperatures.length ≤ 10⁵
30 ≤ temperatures[i] ≤ 100

Clarifying questions4First question: Strictly warmer, or warmer-or-equal?Explore questions

Q1.Strictly warmer, or warmer-or-equal?
Strictly warmer. So I pop while temps[top] < current; an equal temperature does NOT resolve a waiting day.
Q2.What's the answer when no warmer day exists?
0. I pre-fill the result with zeros, so any index left on the stack at the end keeps its default.
Q3.How large is the input — does O(n²) pass?
Up to 10⁵, so O(n²) ≈ 10¹⁰ is too slow. The monotonic stack gives O(n).
Q4.Is the temperature range bounded?
Yes, 30–100. That bounded range even allows an O(n) array-of-next-warmer-index trick, but the monotonic stack is the canonical, range-agnostic answer.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Keep a stack of *indices* whose warmer day hasn't been found yet, with their temperatures in decreasing order. For each new day, while it's warmer than the temperature at the index on top of the stack, pop that index and record the gap (currentIndex − poppedIndex) as its answer. Push the current index. Each index is pushed and popped once → O(n) time, O(n) space. The monotonic stack avoids re-scanning future days.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise a 'next greater element' problem and deploy a monotonic stack of indices for O(n), instead of the obvious O(n²) double loop.

Where candidates slip

Storing temperatures instead of indices (losing the distance), using the wrong monotonic direction, or recomputing answers with a nested scan.

How to stand out

Name the monotonic-stack pattern, explain the amortized O(n) argument (each index pushed/popped once), and note that leftover stack entries correctly default to 0.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Scan Forward (Baseline)	`O(n²)`	`O(1)`	Mention to anchor the O(n²) cost, then improve with the monotonic stack the constraints demand.	Read
2	Monotonic Decreasing Stack (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Say 'monotonic stack of indices — next greater element' and explain amortized O(n).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewday i, temp tstack non-empty AND temps[top] < t?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Scan Forward (Baseline)

TimeO(n²)SpaceO(1)

Mention to anchor the O(n²) cost, then improve with the monotonic stack the constraints demand.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For a single day, how would you find its next warmer day with no extra structures?

2Hint 2Explore hint

For each i, scan j = i+1, i+2, ... until temps[j] > temps[i]; record j - i (or 0 if none).

3Hint 3Explore hint

Correct but O(n²) — a descending run like [100, 99, ..., 30] makes every inner scan long. That repetition is the cue for a stack.

A · Core idea

For every day i, walk forward until a strictly warmer day j is found and store j − i; if none, leave 0.

Why mention it. It directly encodes the definition and confirms the answer format. Why it's too slow. With n up to 10⁵, the nested forward scan is O(n²) ≈ 10¹⁰. The wasted work is re-scanning the same future days for many starting points — exactly what a stack of pending days eliminates.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

temperatures = [73, 74, 75]

i=0 (73)

j=1 → 74 > 73 → ans=1

Stateans[0]=1

Final result[1, 1, 0]

C · Code with teaching comments

Reference implementation previewpublic int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] answer = new int[n]; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) {Explore the full code

solution.javaJava

Brute Force — Scan Forward (Baseline) — reference

3 teaching notes

1
public int[] dailyTemperatures(int[] temperatures) {
2
    int n = temperatures.length;
3
    int[] answer = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        // Scan only later days for a warmer one.
6
        for (int j = i + 1; j < n; j++) {
7
            if (temperatures[j] > temperatures[i]) {
8
                // Distance in days to the next warmer temperature.
9
                answer[i] = j - i;
10
                // Stop at the FIRST warmer day — we want the nearest.
11
                break;
12
            }
13
        }
14
    }
15
    return answer;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The brute force repeatedly re-examines the same cold stretch. If we instead remember the days still waiting for a warmer day, one warm day can resolve many of them at once — turning repeated forward scans into single pops.

ComplexityO(n²) time, O(1) space — For each of n days we may scan up to n later days → O(n²) worst case (e.g. a long descending sequence), constant extra space.

E · Edge cases and pitfalls2O(n²) — times out at n = 10⁵.Explore edge cases

Pitfalls

O(n²) — times out at n = 10⁵.
Forgetting break, which would record the farthest rather than nearest warmer day.

03.2

Approach 2 of 2 · Optimal

Monotonic Decreasing Stack (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Say 'monotonic stack of indices — next greater element' and explain amortized O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Many days might be 'waiting' for a warmer day at once. If you keep those waiting days somewhere, what happens when a warm day finally arrives?

2Hint 2Explore hint

Keep a stack of indices whose answer isn't known yet, kept so their temperatures are decreasing. A new warmer day resolves everything colder on top.

3Hint 3Explore hint

While temps[stack.top] < today, pop and set answer[popped] = today - popped. Then push today. Each index is pushed and popped once → O(n).

A · Core idea

Sweep left to right maintaining a stack of indices of days still awaiting a warmer day, kept in decreasing temperature order from bottom to top.

The invariant. Every index on the stack is a day whose next-warmer-day hasn't been found yet, and their temperatures strictly decrease as you go up the stack. So the top is always the coldest unresolved day so far — and the first one a new warm day can settle.

Processing day `i`. Compare temperatures[i] to the temperature at the index on top. While the top day is colder (temps[top] < temps[i]), day i is its answer: pop the index j and set answer[j] = i − j (the number of days it waited). Repeat — one warm day can resolve a whole descending run of colder days. When the top is not colder (or the stack is empty), push i; it now waits for its own warmer day. The decreasing order is preserved because we only push after popping everything smaller.

Why store indices, not temperatures. The answer is a distance in days, so we need the position to compute i − j. Temperatures alone can't recover that. (The bounded value range also makes indices natural here.)

Unresolved days default to 0. Any index still on the stack after the sweep had no warmer day ahead. Because we initialise answer to all zeros, those positions are already correct — no cleanup needed.

Why it's O(n), not O(n²). It looks like a nested loop, but the inner while only pops indices, and each index can be popped at most once over the entire run (after which it's gone). The total pops plus pushes is bounded by 2n, so the amortized cost per day is constant. This is the hallmark of the monotonic-stack technique: it pays for the inner loop with a global push/pop budget.

Why 'decreasing'. We want the next greater element, so we keep candidates that are still 'looking up' for something bigger — a decreasing stack. (For a next-smaller problem you'd keep an increasing stack and flip the comparison.)

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Array state

i=2 (75)

after pushes/pops, only index 2 waiting

top ↓

[0]

Current pointerResolved stateNot processed

Final result[1, 1, 4, 2, 1, 1, 0, 0]

C · Code with teaching comments

solution.javaJava

Monotonic Decreasing Stack (Optimal) — optimal

6 teaching notes

1
public int[] dailyTemperatures(int[] temperatures) {
2
    int n = temperatures.length;
3
    // Java zero-initialises — unresolved days are already correct.
4
    int[] answer = new int[n];          // defaults to 0
5
    // Store indices so we can compute the day distance.
6
    Deque<Integer> stack = new ArrayDeque<>();   // indices, temps decreasing
7
    for (int i = 0; i < n; i++) {
8
        // Today is warmer than the top waiting day → resolve it. `<` enforces STRICTLY
9
        // warmer.
10
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
11
            // Pop the resolved index.
12
            int j = stack.pop();
13
            // Days waited = current index − that day's index.
14
            answer[j] = i - j;
15
        }
16
        // Today now waits for its own warmer day; invariant stays decreasing.
17
        stack.push(i);
18
    }
19
    return answer;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

A monotonic stack stores only the elements whose answer is still pending, in the order a future element would resolve them. That converts 'for each element, look ahead' from quadratic to linear. The same machine — sometimes increasing, sometimes decreasing, sometimes storing indices for spans — solves Next Greater Element, Online Stock Span, Largest Rectangle in Histogram, and Trapping Rain Water.

ComplexityO(n) time, O(n) space — Each index is pushed exactly once and popped at most once, so the total number of stack operations across the whole run is ≤ 2n. The inner while loop is therefore amortized O(1) per day → O(n) time. The stack can hold up to n indices → O(n) space.

E · Edge cases and pitfalls8temperatures = [30] — Single day, no warmer future → answer [0]; index 0 stays on the stack.Explore edge cases

Edge cases handled

temperatures = [30]Single day, no warmer future → answer [0]; index 0 stays on the stack.
temperatures = [30, 40, 50, 60]Strictly increasing → each day pops the previous immediately → [1,1,1,0].
temperatures = [100, 90, 80]Strictly decreasing → nothing ever pops; all answers stay 0 → [0,0,0].
ties, e.g. [70, 70, 75]Equal temps don't resolve (strict <), so day 0 and day 1 both wait for 75 → [2,1,0].

Pitfalls

Storing temperatures instead of indices — can't compute the day distance.
Using <= instead of < — wrongly resolves equal-temperature days.
Wrong monotonic direction (increasing) — solves next-smaller, not next-greater.
Re-scanning to fill answers instead of trusting the default 0 for leftover indices.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] answer = new int[n]; // defaults to 0 Deque<Integer> stack = new ArrayDeque<>(); // indices, temps decreasing for (int i = 0; i < n; i++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Storing temperatures instead of indices

The answer is the distance in days, which requires positions. A stack of temperatures can't recover how far apart the days are.

Explore the code comparison

Don't write this

stack = []
for i, t in enumerate(temperatures):
    while stack and stack[-1] < t:   # storing temps
        stack.pop()
        # no way to compute i - j here
    stack.append(t)

Write this instead

stack = []                         # store indices
for i, t in enumerate(temperatures):
    while stack and temperatures[stack[-1]] < t:
        j = stack.pop()
        answer[j] = i - j
    stack.append(i)

Non-strict comparison on ties

The problem asks for a strictly warmer day. Using <= pops days with the SAME temperature, recording a warmer-day distance that isn't actually warmer.

Explore the code comparison

Don't write this

while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
    int j = stack.pop();
    answer[j] = i - j;
}

Write this instead

while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
    int j = stack.pop();
    answer[j] = i - j;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic decreasing stack of indices (next greater element)

Code pattern to memorize

stack = []                       # indices, temps decreasing
for i, t in enumerate(temps):
    while stack and temps[stack[-1]] < t:
        j = stack.pop()
        ans[j] = i - j
    stack.append(i)
return ans                        # unresolved indices keep 0

Rules to remember

1Store indices, not temperatures — you need the index distance for the answer.
2Maintain a decreasing stack: pop while temps[top] < current, because the current day is the answer for every colder day still waiting.
3The answer for a popped index j is i − j (days waited), not the temperature.
4Indices never resolved (no warmer day ahead) stay at the default 0 — pre-fill the result with zeros.
5Each index is pushed once and popped at most once → the inner while loop is amortized O(1), giving overall O(n).

Use this pattern when

Next greater / next smaller element, or 'how far until a bigger value'
Span problems: stock span, largest rectangle in histogram, trapping rain water
Any 'for each element, find the nearest later element satisfying a comparison' in O(n)

Choose another pattern when

You need the next greater in *circular* order → still a monotonic stack, but iterate 2n with modulo
Comparison isn't a simple monotone relation → a stack invariant may not hold
You only need one query, not per-element answers → a single scan may suffice

Interview takeaway

A monotonic stack converts an O(n²) 'look ahead for the next bigger value' into O(n) by holding only the *unresolved* candidates in sorted order. Recognising 'next greater element' framing — and storing indices so you can measure distance — is the reusable trick across span and histogram problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternMonotonic stack for next-greater-element / span problems. Recognise it when each element needs the nearest later element satisfying a comparison: keep only unresolved candidates in monotone order and store indices for distances. Same machine as Next Greater Element, Stock Span, and Largest Rectangle in Histogram.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Next Greater Element I
Coming soon
Monotonic stack to precompute next-greater, then map via a hash table.
Next Greater Element II
Coming soon
Circular array — iterate 2n with index % n, same decreasing stack.
Online Stock Span
Coming soon
Monotonic stack storing (price, span) to answer streaming spans in amortized O(1).
Largest Rectangle in Histogram
Coming soon
Monotonic increasing stack of indices to find left/right smaller boundaries.

Same pattern

←

Generate Parentheses

Continue · Next problem

Basic Calculator

mediumStack QueueLC #739Frequently asked

Daily Temperatures

LCPractice

Stack & Queue · 5 of 17 · 9 min

In plain English

Examples

Example 1

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Note: Day 0 (73) waits 1 day for 74; day 2 (75) waits 4 days for 76; days 6 and 7 have no warmer future day → 0.

Example 2

Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]
Note: Strictly increasing — each day's next day is warmer; the last has none.

Example 3

Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]
Note: Each warmer day immediately follows; the peak waits forever → 0.

Constraints

1 ≤ temperatures.length ≤ 10⁵
30 ≤ temperatures[i] ≤ 100

Clarifying questions4First question: Strictly warmer, or warmer-or-equal?Explore questions

Q1.Strictly warmer, or warmer-or-equal?
Strictly warmer. So I pop while temps[top] < current; an equal temperature does NOT resolve a waiting day.
Q2.What's the answer when no warmer day exists?
0. I pre-fill the result with zeros, so any index left on the stack at the end keeps its default.
Q3.How large is the input — does O(n²) pass?
Up to 10⁵, so O(n²) ≈ 10¹⁰ is too slow. The monotonic stack gives O(n).
Q4.Is the temperature range bounded?
Yes, 30–100. That bounded range even allows an O(n) array-of-next-warmer-index trick, but the monotonic stack is the canonical, range-agnostic answer.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise a 'next greater element' problem and deploy a monotonic stack of indices for O(n), instead of the obvious O(n²) double loop.

Where candidates slip

Storing temperatures instead of indices (losing the distance), using the wrong monotonic direction, or recomputing answers with a nested scan.

How to stand out

Name the monotonic-stack pattern, explain the amortized O(n) argument (each index pushed/popped once), and note that leftover stack entries correctly default to 0.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Scan Forward (Baseline)	`O(n²)`	`O(1)`	Mention to anchor the O(n²) cost, then improve with the monotonic stack the constraints demand.	Read
2	Monotonic Decreasing Stack (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Say 'monotonic stack of indices — next greater element' and explain amortized O(n).	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Scan Forward (Baseline)

TimeO(n²)SpaceO(1)

Mention to anchor the O(n²) cost, then improve with the monotonic stack the constraints demand.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For a single day, how would you find its next warmer day with no extra structures?

2Hint 2Explore hint

For each i, scan j = i+1, i+2, ... until temps[j] > temps[i]; record j - i (or 0 if none).

3Hint 3Explore hint

Correct but O(n²) — a descending run like [100, 99, ..., 30] makes every inner scan long. That repetition is the cue for a stack.

A · Core idea

For every day i, walk forward until a strictly warmer day j is found and store j − i; if none, leave 0.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

temperatures = [73, 74, 75]

i=0 (73)

j=1 → 74 > 73 → ans=1

Stateans[0]=1

Final result[1, 1, 0]

C · Code with teaching comments

solution.javaJava

Brute Force — Scan Forward (Baseline) — reference

3 teaching notes

1
public int[] dailyTemperatures(int[] temperatures) {
2
    int n = temperatures.length;
3
    int[] answer = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        // Scan only later days for a warmer one.
6
        for (int j = i + 1; j < n; j++) {
7
            if (temperatures[j] > temperatures[i]) {
8
                // Distance in days to the next warmer temperature.
9
                answer[i] = j - i;
10
                // Stop at the FIRST warmer day — we want the nearest.
11
                break;
12
            }
13
        }
14
    }
15
    return answer;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — For each of n days we may scan up to n later days → O(n²) worst case (e.g. a long descending sequence), constant extra space.

E · Edge cases and pitfalls2O(n²) — times out at n = 10⁵.Explore edge cases

Pitfalls

O(n²) — times out at n = 10⁵.
Forgetting break, which would record the farthest rather than nearest warmer day.

03.2

Approach 2 of 2 · Optimal

Monotonic Decreasing Stack (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Say 'monotonic stack of indices — next greater element' and explain amortized O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Many days might be 'waiting' for a warmer day at once. If you keep those waiting days somewhere, what happens when a warm day finally arrives?

2Hint 2Explore hint

Keep a stack of indices whose answer isn't known yet, kept so their temperatures are decreasing. A new warmer day resolves everything colder on top.

3Hint 3Explore hint

While temps[stack.top] < today, pop and set answer[popped] = today - popped. Then push today. Each index is pushed and popped once → O(n).

A · Core idea

Sweep left to right maintaining a stack of indices of days still awaiting a warmer day, kept in decreasing temperature order from bottom to top.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

Array state

i=2 (75)

after pushes/pops, only index 2 waiting

top ↓

[0]

Current pointerResolved stateNot processed

Final result[1, 1, 4, 2, 1, 1, 0, 0]

C · Code with teaching comments

solution.javaJava

Monotonic Decreasing Stack (Optimal) — optimal

6 teaching notes

1
public int[] dailyTemperatures(int[] temperatures) {
2
    int n = temperatures.length;
3
    // Java zero-initialises — unresolved days are already correct.
4
    int[] answer = new int[n];          // defaults to 0
5
    // Store indices so we can compute the day distance.
6
    Deque<Integer> stack = new ArrayDeque<>();   // indices, temps decreasing
7
    for (int i = 0; i < n; i++) {
8
        // Today is warmer than the top waiting day → resolve it. `<` enforces STRICTLY
9
        // warmer.
10
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
11
            // Pop the resolved index.
12
            int j = stack.pop();
13
            // Days waited = current index − that day's index.
14
            answer[j] = i - j;
15
        }
16
        // Today now waits for its own warmer day; invariant stays decreasing.
17
        stack.push(i);
18
    }
19
    return answer;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8temperatures = [30] — Single day, no warmer future → answer [0]; index 0 stays on the stack.Explore edge cases

Edge cases handled

temperatures = [30]Single day, no warmer future → answer [0]; index 0 stays on the stack.
temperatures = [30, 40, 50, 60]Strictly increasing → each day pops the previous immediately → [1,1,1,0].
temperatures = [100, 90, 80]Strictly decreasing → nothing ever pops; all answers stay 0 → [0,0,0].
ties, e.g. [70, 70, 75]Equal temps don't resolve (strict <), so day 0 and day 1 both wait for 75 → [2,1,0].

Pitfalls

Storing temperatures instead of indices — can't compute the day distance.
Using <= instead of < — wrongly resolves equal-temperature days.
Wrong monotonic direction (increasing) — solves next-smaller, not next-greater.
Re-scanning to fill answers instead of trusting the default 0 for leftover indices.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Storing temperatures instead of indices

The answer is the distance in days, which requires positions. A stack of temperatures can't recover how far apart the days are.

Explore the code comparison

Don't write this

stack = []
for i, t in enumerate(temperatures):
    while stack and stack[-1] < t:   # storing temps
        stack.pop()
        # no way to compute i - j here
    stack.append(t)

Write this instead

stack = []                         # store indices
for i, t in enumerate(temperatures):
    while stack and temperatures[stack[-1]] < t:
        j = stack.pop()
        answer[j] = i - j
    stack.append(i)

Non-strict comparison on ties

The problem asks for a strictly warmer day. Using <= pops days with the SAME temperature, recording a warmer-day distance that isn't actually warmer.

Explore the code comparison

Don't write this

while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
    int j = stack.pop();
    answer[j] = i - j;
}

Write this instead

while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
    int j = stack.pop();
    answer[j] = i - j;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic decreasing stack of indices (next greater element)

Code pattern to memorize

stack = []                       # indices, temps decreasing
for i, t in enumerate(temps):
    while stack and temps[stack[-1]] < t:
        j = stack.pop()
        ans[j] = i - j
    stack.append(i)
return ans                        # unresolved indices keep 0

Rules to remember

1Store indices, not temperatures — you need the index distance for the answer.
2Maintain a decreasing stack: pop while temps[top] < current, because the current day is the answer for every colder day still waiting.
3The answer for a popped index j is i − j (days waited), not the temperature.
4Indices never resolved (no warmer day ahead) stay at the default 0 — pre-fill the result with zeros.
5Each index is pushed once and popped at most once → the inner while loop is amortized O(1), giving overall O(n).

Use this pattern when

Next greater / next smaller element, or 'how far until a bigger value'
Span problems: stock span, largest rectangle in histogram, trapping rain water
Any 'for each element, find the nearest later element satisfying a comparison' in O(n)

Choose another pattern when

You need the next greater in *circular* order → still a monotonic stack, but iterate 2n with modulo
Comparison isn't a simple monotone relation → a stack invariant may not hold
You only need one query, not per-element answers → a single scan may suffice

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Next Greater Element I
Coming soon
Monotonic stack to precompute next-greater, then map via a hash table.
Next Greater Element II
Coming soon
Circular array — iterate 2n with index % n, same decreasing stack.
Online Stock Span
Coming soon
Monotonic stack storing (price, span) to answer streaming spans in amortized O(1).
Largest Rectangle in Histogram
Coming soon
Monotonic increasing stack of indices to find left/right smaller boundaries.

Same pattern

←

Generate Parentheses

Continue · Next problem

Basic Calculator