Stack • Monotonic Stack

The Stock Span Problem

The span of the stock's price today is the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today's price.

Try Interactive Simulator

The Hidden Problem

This is secretly just the Previous Greater Element problem! The span breaks on the exact day that a previous price was strictly greater than today's price.

Index Stack

Instead of storing the actual stock prices in the stack, we MUST store their indices. To calculate the span, we just do `currentIndex - previousGreaterIndex`.

Empty Stack Rule

If the stack becomes empty, it means today's price is higher than ALL previous prices. Thus, the span is simply `currentIndex + 1`.

D0

100

-

D1

80

-

D2

60

-

D3

70

-

D4

60

-

D5

75

-

D6

85

-

Top: Stock Prices | Bottom: Spans

Stack (Stores Indices)

Empty

Code Tracker

:::

1let stack = []; let span = new Array(n);

2for (let i = 0; i < n; i++) {

3 while (stack.length && prices[stack[stack.length - 1]] <= prices[i]) {

4 stack.pop();

5 }

6 if (stack.length === 0) {

7 span[i] = i + 1;

8 } else {

9 span[i] = i - stack[stack.length - 1];

10 }

11 stack.push(i);

12}

13return span;