Online Stock Span

Q: How do you solve Online Stock Span?

Maintain a monotonic decreasing stack where each element is a tuple of (price, span). For each new price, initialize span=1, then pop from the stack while the top price is less than or equal to the current price, adding the popped spans to span. Push the current (price, span) onto the stack and return span. This approach guarantees amortized O(1) time per next() call.

Q: What is the time complexity of Online Stock Span?

O(n). Each price is pushed and popped at most once from the stack, so the total operations over n calls to next() is O(n), resulting in amortized O(1) time per call.

Q: What pattern does Online Stock Span use?

The Pattern: Monotonic Decreasing Stack (Compress Consecutive Smaller Values) The Heuristic: For each day, all we really care about is how many consecutive earlier days had prices less than or equal to today’s price. We use a monotonic decreasing stack to pop earlier days whose prices are less than or equal to today’s and add their stored spans into today’s span, so only earlier days with higher prices remain on the stack. This way we do not need to walk back through every previous day each time we process a new price, because the stack has already collapsed runs of smaller prices into a single span value.

Medium Stacks

Problem

Given a stream of daily stock prices, return the span of the stock's price for the current day, where the span is defined as the maximum number of consecutive days (up to today) the price was less than or equal to today's price.

Calls to next() are made sequentially for each day.
1 ≤ price ≤ 10⁵
At most 10⁴ calls to next() will be made.

Example

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

Output: [1, 1, 1, 2, 1, 4, 6]

Day 1: price=100, no previous days, span=1. Day 2: price=80, previous price 100 > 80, span=1. Day 3: price=60, previous prices 80 and 100 > 60, span=1. Day 4: price=70, previous price 60 <= 70, span includes day 3 and 4, span=2. Day 5: price=60, previous price 70 > 60, span=1. Day 6: price=75, previous prices 60 (day 5), 70 (day 4) <= 75, span includes days 3 to 6, span=4. Day 7: price=85, previous prices 75, 70, 60, 80, 100; all except 100 <= 85, span=6.

Approach

Straightforward Solution

A naive approach would check each previous day one by one until a higher price is found, resulting in O(n) time per query and O(n^2) total time for n days, which is inefficient for large inputs.

Core Observation

The span for a given day depends on how many consecutive previous days had prices less than or equal to the current price. This naturally suggests a data structure that can efficiently track and collapse consecutive days with smaller or equal prices.

Path to Optimal

The key insight is to use a stack that stores pairs of (price, span) in decreasing order of price. When a new price arrives, pop all prices from the stack that are less than or equal to it, accumulating their spans. This collapses multiple days into one operation, enabling amortized O(1) time per query.

Optimal Approach

Maintain a monotonic decreasing stack where each element is a tuple of (price, span). For each new price, initialize span=1, then pop from the stack while the top price is less than or equal to the current price, adding the popped spans to span. Push the current (price, span) onto the stack and return span. This approach guarantees amortized O(1) time per next() call.

Time

O(n)

Each price is pushed and popped at most once from the stack, so the total operations over n calls to next() is O(n), resulting in amortized O(1) time per call.

Space

O(n)

In the worst case, the stack stores all prices if they are strictly decreasing, requiring O(n) auxiliary space.

Pattern Spotlight

Monotonic Decreasing Stack (Compress Consecutive Smaller Values)

For each day, all we really care about is how many consecutive earlier days had prices less than or equal to today’s price. We use a monotonic decreasing stack to pop earlier days whose prices are less than or equal to today’s and add their stored spans into today’s span, so only earlier days with higher prices remain on the stack. This way we do not need to walk back through every previous day each time we process a new price, because the stack has already collapsed runs of smaller prices into a single span value.

Solution

1class StockSpanner:
2    def __init__(self):
3        self.stack = []   
4
5    def next(self, price: int) -> int:
6        span = 1
7
8        while self.stack and self.stack[-1][0] <= price:
9            span += self.stack.pop()[1]
10
11        self.stack.append((price, span))
12        return span

1import java.util.Stack;
2
3public class StockSpanner {
4    private Stack<int[]> stack;
5
6    public StockSpanner() {
7        stack = new Stack<>();
8    }
9
10    public int next(int price) {
11        int span = 1;
12        while (!stack.isEmpty() && stack.peek()[0] <= price) {
13            span += stack.pop()[1];
14        }
15        stack.push(new int[]{price, span});
16        return span;
17    }
18}

1#include <stack>
2#include <utility>
3
4using namespace std;
5
6class StockSpanner {
7private:
8    stack<pair<int, int>> stk;
9
10public:
11    StockSpanner() {
12        // no initialization needed
13    }
14
15    int next(int price) {
16        int span = 1;
17        while (!stk.empty() && stk.top().first <= price) {
18            span += stk.top().second;
19            stk.pop();
20        }
21        stk.push({price, span});
22        return span;
23    }
24};

1class StockSpanner {
  constructor() {
      this.stack = [];
  }
5
  next(price) {
      let span = 1;
      while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
          span += this.stack.pop()[1];
      }
      this.stack.push([price, span]);
      return span;
  }
14}

Step-by-Step Solution

Initialize Monotonic Stack to Store Price and Span Pairs

3	`self.stack = []`

Objective

To create a stack that will hold tuples of (price, span) to efficiently track consecutive days with smaller or equal prices.

Key Insight

Storing both price and its span allows collapsing multiple days into a single stack entry, enabling efficient aggregation of spans when a new price arrives. This data structure is the foundation for the amortized O(1) solution.

Interview Quick-Check

Core Logic

The stack stores pairs of (price, span) in strictly decreasing order of price, enabling efficient span calculation.

Common Pitfalls & Bugs

Forgetting to store the span alongside the price would force repeated counting of consecutive days, losing the amortized efficiency.

Accumulate Span by Popping Smaller or Equal Prices

6span = 1
8while self.stack and self.stack[-1][0] <= price:
9    span += self.stack.pop()[1]

Objective

To compute the span for the current price by collapsing all consecutive previous days with prices less than or equal to it.

Key Insight

By popping all stack entries with prices less than or equal to the current price and adding their spans, the algorithm efficiently skips over multiple days in one step. This collapsing mechanism is what reduces the naive O(n) per query to amortized O(1).

Interview Quick-Check

Core Logic

The while loop pops all stack entries with prices <= current price, accumulating their spans to compute the total span for the current day.

Common Pitfalls & Bugs

Not using a while loop or failing to accumulate spans correctly leads to incorrect span calculation and higher time complexity.

Push Current Price and Span, Then Return Span

11self.stack.append((price, span))
12return span

Objective

To record the current price and its computed span on the stack and return the span as the result for this day.

Key Insight

Pushing the current (price, span) pair maintains the stack's decreasing order invariant and preserves the aggregated span information for future queries. Returning the span completes the query for the current day.

Interview Quick-Check

Core Logic

Appending (price, span) maintains the stack invariant and stores the aggregated span for future computations.

State & Boundaries

Returning span immediately after updating the stack provides the correct span for the current price.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

while self.stack and self.stack[-1][0] <= price:

While the stack is not empty and the top price is less than or equal to the current price, pop from the stack.

This loop collapses all consecutive previous days with prices less than or equal to the current price, enabling efficient aggregation of their spans into the current span.

Line 9 Critical

span += self.stack.pop()[1]

Add the popped span to the current span.

Accumulating the spans of popped entries correctly counts all consecutive days dominated by the current price, ensuring the span reflects the total consecutive days with prices <= current price.

Line 3 Core

self.stack = []

Initialize an empty stack to store (price, span) pairs.

This stack is the core data structure that enables efficient span calculation by maintaining a decreasing sequence of prices and their associated spans.

Line 11 Core

self.stack.append((price, span))

Push the current (price, span) pair onto the stack.

Storing the current price and its aggregated span maintains the stack's decreasing order invariant and prepares for efficient span calculation for future prices.

Line 6 Core

span = 1

Initialize span to 1 for the current price.

Each price has at least a span of 1 (the current day itself), serving as the base count before accumulating spans from previous days.

Line 12 Core

return span

Return the computed span for the current price.

Returning the span completes the query, providing the maximum number of consecutive days with prices less than or equal to the current price.

Test Your Understanding

Why does popping all smaller or equal prices from the stack and accumulating their spans correctly compute the current day's span?

Because the stack maintains prices in decreasing order, popping smaller or equal prices aggregates all consecutive previous days that the current price dominates, ensuring the span counts all consecutive days with prices less than or equal to the current price.

Don't just read it. Drill it.

Reconstruct Online Stock Span from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Online Stock Span drill

or drill a free problem

1	`class StockSpanner:`
2	`def __init__(self):`
3	`self.stack = []`
4
5	`def next(self, price: int) -> int:`
6	`span = 1`
7
8	`while self.stack and self.stack[-1][0] <= price:`
9	`span += self.stack.pop()[1]`
10
11	`self.stack.append((price, span))`
12	`return span`

1	`import java.util.Stack;`
2
3	`public class StockSpanner {`
4	`private Stack<int[]> stack;`
5
6	`public StockSpanner() {`
7	`stack = new Stack<>();`
8	`}`
9
10	`public int next(int price) {`
11	`int span = 1;`
12	`while (!stack.isEmpty() && stack.peek()[0] <= price) {`
13	`span += stack.pop()[1];`
14	`}`
15	`stack.push(new int[]{price, span});`
16	`return span;`
17	`}`
18	`}`

1	`#include <stack>`
2	`#include <utility>`
3
4	`using namespace std;`
5
6	`class StockSpanner {`
7	`private:`
8	`stack<pair<int, int>> stk;`
9
10	`public:`
11	`StockSpanner() {`
12	`// no initialization needed`
13	`}`
14
15	`int next(int price) {`
16	`int span = 1;`
17	`while (!stk.empty() && stk.top().first <= price) {`
18	`span += stk.top().second;`
19	`stk.pop();`
20	`}`
21	`stk.push({price, span});`
22	`return span;`
23	`}`
24	`};`

1	`class StockSpanner {`
2	`constructor() {`
3	`this.stack = [];`
4	`}`
5
6	`next(price) {`
7	`let span = 1;`
8	`while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {`
9	`span += this.stack.pop()[1];`
10	`}`
11	`this.stack.push([price, span]);`
12	`return span;`
13	`}`
14	`}`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Monotonic Stack to Store Price and Span Pairs

Accumulate Span by Popping Smaller or Equal Prices

Push Current Price and Span, Then Return Span

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.