Online Stock Span — Monotonic Stack with Span Accumulation

Problem Statement#

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day. The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going to the left) for which the stock price was less than or equal to the price of that day.

Implement the StockSpanner class with a next(price) method that returns the span of the stock's price for the current day.

Constraints:

• 1 <= price <= 10^5
• At most 10^4 calls will be made to next.

Input:  ["StockSpanner","next","next","next","next","next","next","next"]
        [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation:
next(100) → span=1 (no prev ≤ 100 other than today)
next(80)  → span=1
next(60)  → span=1
next(70)  → span=2 (70 ≥ 60)
next(60)  → span=1
next(75)  → span=4 (75 ≥ 60,70,60 and today)
next(85)  → span=6 (85 ≥ all previous 6 days)

Input:  ["StockSpanner","next","next","next"]
        [[],[50],[50],[50]]
Output: [null,1,2,3]
Explanation: Each day ≥ 50 accumulates the span of all previous ≥ 50 days.

Input:  ["StockSpanner","next","next","next","next"]
        [[],[100],[10],[20],[30]]
Output: [null,1,1,2,3]

Why This Problem Matters#

LC 901 is a streaming design problem that combines the monotonic stack pattern with span accumulation — a key technique where you merge adjacent "resolved" spans into a single stack entry. This compression is what makes the algorithm O(1) amortized despite the while loop.

This problem is asked at Amazon (trading systems), Google (analytics), and Bloomberg (financial data). It represents a class of streaming problems where:

• You receive data one element at a time (online algorithm).
• You need an answer for each element immediately.
• Naive O(n) per query is too slow (O(n^2) overall); O(1) amortized per query is required.

The span accumulation trick also appears in Jump Game VI (LC 1696) and similar "range sum with monotonic structure" problems.

The Core Insight#

Naive approach: For each next(price) call, scan backward until you find a price greater than price. This is O(n) per call, O(n^2) total.

Monotonic stack with span accumulation: Maintain a stack of (price, span) pairs in decreasing order of price. When next(price) is called:

1. Start with span = 1 (today itself).
2. While the stack top's price is less than or equal to today's price, pop it and add its span to today's span. This "absorbs" all consecutive previous days that are also <= price.
3. Push (price, span) onto the stack.
4. Return span.

Why this works: When a day is popped, it means today is greater than or equal to that day. The popped day's span already accounts for all consecutive prior days <= that popped day — which are also <= today. So we can absorb the span entirely without revisiting those days.

This is the key compression: instead of re-examining every day in the span, we summarize it into a single (price, span) entry.

Visual Dry Run#

Prices: 100, 80, 60, 70, 60, 75, 85

Solution (Optimal)#

# Python — monotonic decreasing stack with span accumulation
# Amortized O(1) per call, O(n) total space
class StockSpanner:
    def __init__(self):
        # Stack stores (price, span) pairs in monotonically decreasing price order
        self.stack = []
 
    def next(self, price: int) -> int:
        span = 1  # today itself always counts
 
        # Absorb all consecutive previous days with price <= today
        # Each popped (prev_price, prev_span) represents a block of prev_span days
        # all with price <= prev_price <= price
        while self.stack and self.stack[-1][0] <= price:
            _, prev_span = self.stack.pop()
            span += prev_span  # absorb the entire span of the popped entry
 
        self.stack.append((price, span))
        return span

// JavaScript — monotonic decreasing stack with span accumulation
class StockSpanner {
    constructor() {
        this.stack = [];  // array of [price, span] pairs
    }
 
    next(price) {
        let span = 1;
 
        // Absorb all previous days with price <= today
        while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
            const [, prevSpan] = this.stack.pop();
            span += prevSpan;
        }
 
        this.stack.push([price, span]);
        return span;
    }
}

Complexity:

Common Mistakes#

1. Storing only prices, not spans. If you store only (price) in the stack, you must re-examine all the days that were previously absorbed when you pop. This defeats the compression and makes it O(n) per call. Always store (price, span) pairs.

2. Using strict less-than instead of less-than-or-equal. The span counts days where price is less than or equal to today. The pop condition must be stack[-1][0] <= price, not < price. Using strict less-than misses equal-price days in the span.

3. Not starting span at 1. Today itself is always part of the span. Starting span = 0 will always under-count by 1.

4. Treating this as a one-shot array problem. This is a streaming (online) problem — you cannot pre-process all prices. You must answer each next() call before the next one arrives.

5. Confusing span with the index position. The span is a count of consecutive days, not an index or distance. It starts at 1 (just today) and grows as you absorb previous spans.

Interview Tips#

• Explain the amortized O(1) argument: "Each day is pushed once and popped at most once. Over n calls, total push+pop operations is at most 2n → O(n) total → amortized O(1) per call."
• Emphasize the (price, span) pair: "Storing just the price is insufficient — I need to remember how many days each entry represents so I can absorb them in O(1) without revisiting them."
• The <= comparison is intentional: "The span counts days with price less than or equal to today — equal days are absorbed too."

Follow-up Questions#

1. Stock Span with strict greater-than. Replace <= with < in the pop condition. Days with equal prices are not absorbed.
2. Maximum span across all days. Track max_span = max(max_span, span) inside each next() call.
3. Sliding window stock span (last k days only). Add index tracking; pop when the popped index is more than k days ago.
4. Span of minimum (days where price >= today). Use a monotonic increasing stack (pop when stack[-1][0] >= price).
5. Return the actual price series that constitutes the span. Store the full series — but this would make the algorithm O(n) per call in the worst case.

Key Takeaways#

• Span accumulation: store (price, span) pairs on the stack. When a stack entry is popped, its span is added to the current span — avoiding re-examination of absorbed days.
• The pop condition is stack[-1][0] <= price (note less-than-or-equal) because the span includes days where the price was equal to or less than today.
• Amortized O(1) per call: each entry is pushed once and popped at most once, regardless of how many entries are absorbed per call.
• Start span = 1 to count today itself before any absorption.
• This problem is the streaming (online) version of the "previous greater element" problem — the stack eliminates the need to re-scan backward on every call.
• The span accumulation trick reappears in Jump Game VI (LC 1696) and Sum of Subarray Minimums (LC 907) — recognize it as a compression technique for monotonic structures.