Loading…

mediumArraysFrequently asked

Stock Span

Q: How do you solve Stock Span using the Backward Rescan Per Day (Baseline) approach?

When to use it: State it to anchor the definition, then point out the O(n²) blowup on increasing prices and optimize. For each day, walk backward over previous days while their price is `≤` today's, counting as you go, and stop at the first day with a strictly higher price. **Why it directly encodes the definition.** The span literally *is* the length of the backward run of `≤`-priced days, so the backward loop is a faithful translation. Run it on the sample and it produces the right spans — useful as a correctness oracle. **Why it degrades to O(n²).** Consider strictly increasing prices `[10, 20, 30, 40]`. Day 3 rescans days 2, 1, 0; day 2 rescans 1, 0; and so on — the backward walks add up to `n(n−1)/2`. For `n = 10⁵` that's ~`5 × 10⁹` steps, far too slow. **The redundancy that points to the fix.** When day 5's price absorbs day 4, it already 'knows' how far day 4 reached back. The backward rescan throws that knowledge away and re-walks it. If each day instead recorded *its own span*, a later taller day could swallow that whole run in a single step instead of re-counting it. That memo — carry the span and absorb it — is exactly the monotonic stack. Time complexity: O(n²). Space complexity: O(1) extra.

Two Pointers · 30 of 30 · 9 min

The span of a stock's price on day i is the maximum number of consecutive days (ending on day i, counting day i) for which the price was less than or equal to the price on day i.

Given the daily prices, return the span for each day. In the streaming version, return each span as its price arrives.

In plain English

For each day, count backward over the run of days whose price didn't exceed today's, stopping at the first day with a strictly higher price. The challenge is doing this without an O(n²) backward rescan per day.

Examples

Example 1

Input: prices = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Note: Day 5 (75): 75 ≥ 60,70,60 going back until 80 > 75 stops it → span 4. Day 6 (85): 85 ≥ 75,60,70,60,80 until 100 > 85 → span 6.

Example 2

Input: prices = [10, 20, 30, 40]
Output: [1, 2, 3, 4]
Note: Strictly increasing — each day's price beats all previous, so spans grow 1,2,3,4.

Example 3

Input: prices = [40, 30, 20, 10]
Output: [1, 1, 1, 1]
Note: Strictly decreasing — each day is lower than the previous, so every span is just 1.

Constraints

1 ≤ prices.length ≤ 10⁵
1 ≤ prices[i] ≤ 10⁵
Span values are in [1, i + 1] for day i

Clarifying questions4First question: Are equal prices included in the span?Explore questions

Q1.Are equal prices included in the span?
Yes — the definition is 'less than or equal', so consecutive equal-or-lower days count. I pop on <= so equals are absorbed.
Q2.Is this a one-shot array or a stream?
If prices arrive one at a time (the classic 'StockSpanner' design), I keep a stack across calls and return each span on arrival. The core logic is identical.
Q3.Does the span include today?
Yes — today always counts, so the minimum span is 1. I initialize span to 1 before popping.
Q4.Any ties on the very first day?
Day 0 always has span 1 (no earlier days). The stack starts empty, so no pops happen.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The span at day i is how many consecutive days back (including today) the price was ≤ today's price. Brute force walks backward each day for O(n²). The optimal keeps a monotonic decreasing stack of (price, span): pop every day whose price ≤ today, absorbing their spans, then today's span is 1 + the popped spans. O(n) amortized.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize 'count back to the previous greater price' as a monotonic-stack problem and store spans (not indices) so each element is touched once for amortized O(n).

Where candidates slip

Re-scanning backward each day (O(n²)), using strict < so equal prices break the count, or storing indices and then re-deriving spans awkwardly.

How to stand out

Name it as previous-greater-element, prove the O(n) amortization (each element pushed/popped once), and handle the streaming variant where prices arrive one at a time.

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	Backward Rescan Per Day (Baseline)	`O(n²)`	`O(1) extra`	State it to anchor the definition, then point out the O(n²) blowup on increasing prices and optimize.	Read
2	Monotonic Decreasing Stack (Optimal)Optimal	`O(n) amortized`	`O(n)`	The answer they want. Frame it as 'previous greater element via a monotonic stack, storing spans so we absorb runs in one pop'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCompute daily spansRescan back each day?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

Backward Rescan Per Day (Baseline)

TimeO(n²)SpaceO(1) extra

State it to anchor the definition, then point out the O(n²) blowup on increasing prices and optimize.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The span is just 'how many days back was the price still ≤ today before someone beat it'. What's the most direct way to count that?

2Hint 2Explore hint

For each day i, walk backward while prices[j] <= prices[i], counting days, and stop at the first strictly greater price.

3Hint 3Explore hint

On an increasing sequence each day rescans everything before it — that's 1 + 2 + … + n = O(n²). Can you avoid rescanning days you've already resolved?

A · Core idea

For each day, walk backward over previous days while their price is ≤ today's, counting as you go, and stop at the first day with a strictly higher price.

Why it directly encodes the definition. The span literally is the length of the backward run of ≤-priced days, so the backward loop is a faithful translation. Run it on the sample and it produces the right spans — useful as a correctness oracle.

Why it degrades to O(n²). Consider strictly increasing prices [10, 20, 30, 40]. Day 3 rescans days 2, 1, 0; day 2 rescans 1, 0; and so on — the backward walks add up to n(n−1)/2. For n = 10⁵ that's ~`5 × 10⁹` steps, far too slow.

The redundancy that points to the fix. When day 5's price absorbs day 4, it already 'knows' how far day 4 reached back. The backward rescan throws that knowledge away and re-walks it. If each day instead recorded its own span, a later taller day could swallow that whole run in a single step instead of re-counting it. That memo — carry the span and absorb it — is exactly the monotonic stack.

B · Visual dry run

Interactive dry run

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

prices = [100, 80, 60, 70]

Array state

day 3 (70)

60 ≤ 70 count, 80 > 70 stop → span 2

100

[0]

j ↓

[1]

[2]

i ↓

[3]

Current pointerResolved stateNot processed

Final result[1, 1, 1, 2]

C · Code with teaching comments

Reference implementation previewpublic int[] stockSpan(int[] prices) { int n = prices.length; int[] span = new int[n]; for (int i = 0; i < n; i++) { int count = 1;Explore the full code

solution.javaJava

Backward Rescan Per Day (Baseline) — reference

3 teaching notes

1
public int[] stockSpan(int[] prices) {
2
    int n = prices.length;
3
    int[] span = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        int count = 1;
6
        int j = i - 1;
7
        // <= so equal-priced days are included; stop at the first strictly greater
8
        // price.
9
        while (j >= 0 && prices[j] <= prices[i]) {
10
            // Each qualifying earlier day extends the span.
11
            count++;
12
            j--;
13
        }
14
        // count starts at 1 because today always counts.
15
        span[i] = count;
16
    }
17
    return span;
18
}

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

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

The brute force re-walks runs it has already measured. Realizing that a day, once dominated by a taller later day, will never be an answer again — and that you can absorb its precomputed span in one jump — is the leap to O(n).

ComplexityO(n²) time, O(1) extra space — For day i the backward walk can traverse up to i prior days. Summed over all i this is n(n+1)/2 → O(n²). Only a counter is stored beyond the output.

E · Edge cases and pitfalls3O(n²) on increasing prices — times out at n = 10⁵.Explore edge cases

Pitfalls

O(n²) on increasing prices — times out at n = 10⁵.
Using < and breaking the count on equal prices.
Forgetting today counts (span minimum is 1).

03.2

Approach 2 of 2 · Optimal

Monotonic Decreasing Stack (Optimal)

TimeO(n) amortizedSpaceO(n)

The answer they want. Frame it as 'previous greater element via a monotonic stack, storing spans so we absorb runs in one pop'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When today's price dominates several recent days, those days can never be the 'stopping point' for any future day either. What can you do with them permanently?

2Hint 2Explore hint

Keep a stack of days in decreasing price order. For each new price, pop every day whose price is ≤ today and add up their spans.

3Hint 3Explore hint

Push (price, accumulatedSpan) where the span is 1 plus the spans of everyone you just popped. Each element is pushed once and popped at most once → O(n) total.

A · Core idea

Maintain a stack of (price, span) pairs kept in strictly decreasing price order from bottom to top. For each new day, start span = 1, then while the stack's top price is ≤ today's price, pop it and add its stored span to today's. Push (todayPrice, span); that span is the answer for today.

Why the stack is monotonic and what it represents. From bottom to top the stack holds the 'candidate stoppers' — earlier days with strictly higher prices that could halt a future span, each paired with the span it accumulated. Any day whose price is ≤ a later day is dominated: it can never be the first greater price for anything that comes after, so it's removed permanently. That removal keeps the stack decreasing.

Why we store the span, not just the price. When today pops day k, day k had already counted its own backward run (its span). Today's run extends through day k's entire run in one shot, so adding day k's span — rather than re-walking those days — is what collapses the work. After popping all ≤ days, span equals 1 (today) + sum of absorbed spans, which is precisely the distance back to the first strictly greater price.

Why `≤` and not `<` when popping. The definition counts days with price less than or equal to today. So an equal-priced earlier day must be absorbed into today's span, which means you pop on ≤. Use strict < and equal prices wrongly halt the span, undercounting.

Why it's O(n) amortized. A single day might pop many entries, tempting you to call it O(n²). But each price is pushed exactly once and can be popped at most once in its lifetime — once gone, it never returns. So across all n days the total pop count is bounded by n. Total work is O(n), even though individual days vary. This amortized argument is the heart of the answer.

Why it suits streaming. Nothing requires the full array up front. Keep the stack as state and, when a new price arrives, run the same pop-and-push to return that day's span immediately — the classic 'StockSpanner' online design.

The equivalent index view. span = i − (index of previous strictly greater element). You could instead keep a stack of indices and a prevGreater[] array; the (price, span) formulation just folds that bookkeeping into the stack so no index arithmetic is needed.

B · Visual dry run

Interactive dry run

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

prices = [100, 80, 60, 70, 60, 75, 85]

Array state

day 6 (85)

pop 75→+4, pop 80→+1, stop at 100 → span 6

100

[0]

[1]

[2]

[3]

[4]

[5]

i ↓

[6]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Monotonic Decreasing Stack (Optimal) — optimal

4 teaching notes

1
public int[] stockSpan(int[] prices) {
2
    int n = prices.length;
3
    int[] span = new int[n];
4
    Deque<int[]> stack = new ArrayDeque<>(); // each entry: {price, span}
5
    for (int i = 0; i < n; i++) {
6
        int s = 1;
7
        // <= pops days today dominates, including equal prices.
8
        while (!stack.isEmpty() && stack.peek()[0] <= prices[i]) {
9
            s += stack.pop()[1];   // absorb the popped day's whole span
10
        }
11
        // Today becomes the new candidate stopper with its full span.
12
        stack.push(new int[]{prices[i], s});
13
        span[i] = s;
14
    }
15
    return span;
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) amortized timeO(n) spaceOpen the invariant and proofExplore the proof

A day that's been overtaken by a taller later day is dead — it can never stop a future span — so you discard it and inherit its span. 'Discard dominated candidates, reuse their precomputed answer' is the monotonic-stack pattern shared by Daily Temperatures, Next Greater Element, and Largest Rectangle in Histogram.

ComplexityO(n) amortized time, O(n) space — Each price is pushed exactly once and popped at most once across the whole run, so the total number of stack operations is at most 2n → O(n) amortized, even though a single day's pop loop can be long. The stack holds up to n entries → O(n) space.

E · Edge cases and pitfalls7prices = [10, 20, 30, 40] — Each day pops all prior days (each dominated), spans grow 1,2,3,4 — yet total pops are still ≤ n.Explore edge cases

Edge cases handled

prices = [10, 20, 30, 40]Each day pops all prior days (each dominated), spans grow 1,2,3,4 — yet total pops are still ≤ n.
prices = [40, 30, 20, 10]No pops ever (strictly decreasing); every span is 1, stack grows to n.
prices = [50, 50, 50]Equal prices: each pops the previous (<=), spans become 1, 2, 3.

Pitfalls

Storing indices but forgetting to translate to spans, or using < so equal prices don't absorb.
Calling it O(n²) because one day pops a lot — it's O(n) amortized (each element popped once).
Re-pushing popped days, breaking the push-once/pop-once invariant.
Initializing span at 0 instead of 1 — today must count.

Practice

Try the solution yourself

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

Editable code previewpublic int[] stockSpan(int[] prices) { int n = prices.length; int[] span = new int[n]; Deque<int[]> stack = new ArrayDeque<>(); // each entry: {price, span} 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.

Strict comparison drops equal prices

The span includes days with price ≤ today. With strict <, an equal-priced earlier day halts the span and undercounts.

Explore the code comparison

Don't write this

while stack and stack[-1][0] < price:   # misses equal prices
    s += stack.pop()[1]

Write this instead

while stack and stack[-1][0] <= price:
    s += stack.pop()[1]

Not accumulating spans on the stack

If you only store prices and pop, you lose the count of days each popped entry represented, forcing an O(n) recount per pop.

Explore the code comparison

Don't write this

while (!stack.isEmpty() && stack.peek() <= prices[i]) {
    stack.pop();
    s++;   // only +1 per pop — wrong, ignores the popped day's own span
}

Write this instead

while (!stack.isEmpty() && stack.peek()[0] <= prices[i]) {
    s += stack.pop()[1];   // absorb the full span
}

Span initialized at 0

Today always counts toward its own span, so the base value is 1. Starting at 0 undercounts every day by one.

Explore the code comparison

Don't write this

s = 0
while stack and stack[-1][0] <= price:
    s += stack.pop()[1]

Write this instead

s = 1
while stack and stack[-1][0] <= price:
    s += stack.pop()[1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic decreasing stack storing (price, span); previous-greater-element in disguise

Code pattern to memorize

span = 1
while stack and stack.top.price <= today:
    span += stack.pop().span
stack.push((today, span))

Rules to remember

1Span counts back to (and stops at) the first strictly greater previous price. Use <= when popping so equal prices are absorbed into today's span.
2Store the span (count), not the index, on the stack — popping absorbs the popped element's whole span in one move, which is what makes it O(n).
3The stack stays monotonically decreasing in price; that invariant is why each element is pushed and popped at most once.
4Span is always at least 1 (today itself counts). Initialize span = 1 before popping.
5Equivalently: span = i − (index of previous strictly greater element). The (price, span) form avoids storing indices but means the same thing.

Use this pattern when

Online/streaming: spans must be reported as each new price arrives
'How far back until a value larger than the current one' — previous greater element
Any nearest-greater / nearest-smaller scan reducible to a monotonic stack
When a naive backward scan per element is O(n²) and you need O(n)

Choose another pattern when

You need the next greater element to the right → still a monotonic stack, but scan direction/comparison flips
You need spans only once over a static array → a prev-greater index array is equivalent and maybe clearer
The condition isn't 'greater/smaller' but arbitrary → a stack may not apply

Interview takeaway

Stock span is the streaming face of 'previous greater element'. The monotonic stack works because once a day is dominated by a taller later day, it can never be the answer again — so you pop it for good and absorb its span, giving amortized O(1) per day.

Continue

Transfer the pattern to another problem

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

Transferable patternMonotonic decreasing stack solving previous-greater-element, with spans accumulated on the stack so dominated days are absorbed in one pop. The reusable instinct: discard candidates that can never be the answer again and reuse their precomputed result — the engine behind Daily Temperatures, Next Greater Element, and histogram problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Find the Duplicate Number

mediumArraysFrequently asked

Stock Span

Two Pointers · 30 of 30 · 9 min

The span of a stock's price on day i is the maximum number of consecutive days (ending on day i, counting day i) for which the price was less than or equal to the price on day i.

Given the daily prices, return the span for each day. In the streaming version, return each span as its price arrives.

In plain English

Examples

Example 1

Input: prices = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Note: Day 5 (75): 75 ≥ 60,70,60 going back until 80 > 75 stops it → span 4. Day 6 (85): 85 ≥ 75,60,70,60,80 until 100 > 85 → span 6.

Example 2

Input: prices = [10, 20, 30, 40]
Output: [1, 2, 3, 4]
Note: Strictly increasing — each day's price beats all previous, so spans grow 1,2,3,4.

Example 3

Input: prices = [40, 30, 20, 10]
Output: [1, 1, 1, 1]
Note: Strictly decreasing — each day is lower than the previous, so every span is just 1.

Constraints

1 ≤ prices.length ≤ 10⁵
1 ≤ prices[i] ≤ 10⁵
Span values are in [1, i + 1] for day i

Clarifying questions4First question: Are equal prices included in the span?Explore questions

Q1.Are equal prices included in the span?
Yes — the definition is 'less than or equal', so consecutive equal-or-lower days count. I pop on <= so equals are absorbed.
Q2.Is this a one-shot array or a stream?
If prices arrive one at a time (the classic 'StockSpanner' design), I keep a stack across calls and return each span on arrival. The core logic is identical.
Q3.Does the span include today?
Yes — today always counts, so the minimum span is 1. I initialize span to 1 before popping.
Q4.Any ties on the very first day?
Day 0 always has span 1 (no earlier days). The stack starts empty, so no pops happen.

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 recognize 'count back to the previous greater price' as a monotonic-stack problem and store spans (not indices) so each element is touched once for amortized O(n).

Where candidates slip

Re-scanning backward each day (O(n²)), using strict < so equal prices break the count, or storing indices and then re-deriving spans awkwardly.

How to stand out

Name it as previous-greater-element, prove the O(n) amortization (each element pushed/popped once), and handle the streaming variant where prices arrive one at a time.

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	Backward Rescan Per Day (Baseline)	`O(n²)`	`O(1) extra`	State it to anchor the definition, then point out the O(n²) blowup on increasing prices and optimize.	Read
2	Monotonic Decreasing Stack (Optimal)Optimal	`O(n) amortized`	`O(n)`	The answer they want. Frame it as 'previous greater element via a monotonic stack, storing spans so we absorb runs in one pop'.	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

Backward Rescan Per Day (Baseline)

TimeO(n²)SpaceO(1) extra

State it to anchor the definition, then point out the O(n²) blowup on increasing prices and optimize.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The span is just 'how many days back was the price still ≤ today before someone beat it'. What's the most direct way to count that?

2Hint 2Explore hint

For each day i, walk backward while prices[j] <= prices[i], counting days, and stop at the first strictly greater price.

3Hint 3Explore hint

On an increasing sequence each day rescans everything before it — that's 1 + 2 + … + n = O(n²). Can you avoid rescanning days you've already resolved?

A · Core idea

For each day, walk backward over previous days while their price is ≤ today's, counting as you go, and stop at the first day with a strictly higher price.

B · Visual dry run

Interactive dry run

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

prices = [100, 80, 60, 70]

Array state

day 3 (70)

60 ≤ 70 count, 80 > 70 stop → span 2

100

[0]

j ↓

[1]

[2]

i ↓

[3]

Current pointerResolved stateNot processed

Final result[1, 1, 1, 2]

C · Code with teaching comments

Reference implementation previewpublic int[] stockSpan(int[] prices) { int n = prices.length; int[] span = new int[n]; for (int i = 0; i < n; i++) { int count = 1;Explore the full code

solution.javaJava

Backward Rescan Per Day (Baseline) — reference

3 teaching notes

1
public int[] stockSpan(int[] prices) {
2
    int n = prices.length;
3
    int[] span = new int[n];
4
    for (int i = 0; i < n; i++) {
5
        int count = 1;
6
        int j = i - 1;
7
        // <= so equal-priced days are included; stop at the first strictly greater
8
        // price.
9
        while (j >= 0 && prices[j] <= prices[i]) {
10
            // Each qualifying earlier day extends the span.
11
            count++;
12
            j--;
13
        }
14
        // count starts at 1 because today always counts.
15
        span[i] = count;
16
    }
17
    return span;
18
}

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

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

ComplexityO(n²) time, O(1) extra space — For day i the backward walk can traverse up to i prior days. Summed over all i this is n(n+1)/2 → O(n²). Only a counter is stored beyond the output.

E · Edge cases and pitfalls3O(n²) on increasing prices — times out at n = 10⁵.Explore edge cases

Pitfalls

O(n²) on increasing prices — times out at n = 10⁵.
Using < and breaking the count on equal prices.
Forgetting today counts (span minimum is 1).

03.2

Approach 2 of 2 · Optimal

Monotonic Decreasing Stack (Optimal)

TimeO(n) amortizedSpaceO(n)

The answer they want. Frame it as 'previous greater element via a monotonic stack, storing spans so we absorb runs in one pop'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When today's price dominates several recent days, those days can never be the 'stopping point' for any future day either. What can you do with them permanently?

2Hint 2Explore hint

Keep a stack of days in decreasing price order. For each new price, pop every day whose price is ≤ today and add up their spans.

3Hint 3Explore hint

Push (price, accumulatedSpan) where the span is 1 plus the spans of everyone you just popped. Each element is pushed once and popped at most once → O(n) total.

A · Core idea

B · Visual dry run

Interactive dry run

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

prices = [100, 80, 60, 70, 60, 75, 85]

Array state

day 6 (85)

pop 75→+4, pop 80→+1, stop at 100 → span 6

100

[0]

[1]

[2]

[3]

[4]

[5]

i ↓

[6]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Monotonic Decreasing Stack (Optimal) — optimal

4 teaching notes

1
public int[] stockSpan(int[] prices) {
2
    int n = prices.length;
3
    int[] span = new int[n];
4
    Deque<int[]> stack = new ArrayDeque<>(); // each entry: {price, span}
5
    for (int i = 0; i < n; i++) {
6
        int s = 1;
7
        // <= pops days today dominates, including equal prices.
8
        while (!stack.isEmpty() && stack.peek()[0] <= prices[i]) {
9
            s += stack.pop()[1];   // absorb the popped day's whole span
10
        }
11
        // Today becomes the new candidate stopper with its full span.
12
        stack.push(new int[]{prices[i], s});
13
        span[i] = s;
14
    }
15
    return span;
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) amortized timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7prices = [10, 20, 30, 40] — Each day pops all prior days (each dominated), spans grow 1,2,3,4 — yet total pops are still ≤ n.Explore edge cases

Edge cases handled

prices = [10, 20, 30, 40]Each day pops all prior days (each dominated), spans grow 1,2,3,4 — yet total pops are still ≤ n.
prices = [40, 30, 20, 10]No pops ever (strictly decreasing); every span is 1, stack grows to n.
prices = [50, 50, 50]Equal prices: each pops the previous (<=), spans become 1, 2, 3.

Pitfalls

Storing indices but forgetting to translate to spans, or using < so equal prices don't absorb.
Calling it O(n²) because one day pops a lot — it's O(n) amortized (each element popped once).
Re-pushing popped days, breaking the push-once/pop-once invariant.
Initializing span at 0 instead of 1 — today must count.

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.

Strict comparison drops equal prices

The span includes days with price ≤ today. With strict <, an equal-priced earlier day halts the span and undercounts.

Explore the code comparison

Don't write this

while stack and stack[-1][0] < price:   # misses equal prices
    s += stack.pop()[1]

Write this instead

while stack and stack[-1][0] <= price:
    s += stack.pop()[1]

Not accumulating spans on the stack

If you only store prices and pop, you lose the count of days each popped entry represented, forcing an O(n) recount per pop.

Explore the code comparison

Don't write this

while (!stack.isEmpty() && stack.peek() <= prices[i]) {
    stack.pop();
    s++;   // only +1 per pop — wrong, ignores the popped day's own span
}

Write this instead

while (!stack.isEmpty() && stack.peek()[0] <= prices[i]) {
    s += stack.pop()[1];   // absorb the full span
}

Span initialized at 0

Today always counts toward its own span, so the base value is 1. Starting at 0 undercounts every day by one.

Explore the code comparison

Don't write this

s = 0
while stack and stack[-1][0] <= price:
    s += stack.pop()[1]

Write this instead

s = 1
while stack and stack[-1][0] <= price:
    s += stack.pop()[1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic decreasing stack storing (price, span); previous-greater-element in disguise

Code pattern to memorize

span = 1
while stack and stack.top.price <= today:
    span += stack.pop().span
stack.push((today, span))

Rules to remember

1Span counts back to (and stops at) the first strictly greater previous price. Use <= when popping so equal prices are absorbed into today's span.
2Store the span (count), not the index, on the stack — popping absorbs the popped element's whole span in one move, which is what makes it O(n).
3The stack stays monotonically decreasing in price; that invariant is why each element is pushed and popped at most once.
4Span is always at least 1 (today itself counts). Initialize span = 1 before popping.
5Equivalently: span = i − (index of previous strictly greater element). The (price, span) form avoids storing indices but means the same thing.

Use this pattern when

Online/streaming: spans must be reported as each new price arrives
'How far back until a value larger than the current one' — previous greater element
Any nearest-greater / nearest-smaller scan reducible to a monotonic stack
When a naive backward scan per element is O(n²) and you need O(n)

Choose another pattern when

You need the next greater element to the right → still a monotonic stack, but scan direction/comparison flips
You need spans only once over a static array → a prev-greater index array is equivalent and maybe clearer
The condition isn't 'greater/smaller' but arbitrary → a stack may not apply

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

Same pattern

←

Find the Duplicate Number