Problem Overview
LeetCode 901 — Online Stock Span — asks you to design a StockSpanner class with a single method next(price) that returns the span of the stock price for that day. The span is the maximum number of consecutive days (including today) for which the price was less than or equal to today's price.
For example, if prices are [100, 80, 60, 70, 60, 75, 85], the spans are [1, 1, 1, 2, 1, 4, 6]. The price 75 has span 4 because 60, 70, 60, 75 are all <= 75 going backwards. The price 85 has span 6 because 75, 60, 70, 60, 80 are all <= 85.
The naive approach for each next() call scans backwards through all previous prices to count the span. This gives O(n) per call and O(n^2) total for n calls. A monotonic stack reduces the amortized cost to O(1) per call.
- Design a StockSpanner class with method next(price)
- Span = consecutive days where price <= today's price (including today)
- Process prices one at a time in an online fashion
- Return the span after each price is processed
- Total of at most 10^4 calls to next()
Monotonic Decreasing Stack
Maintain a stack of (price, span) pairs in monotonically decreasing order of price. When next(price) is called, initialize span = 1 (counting today). Then pop all entries from the stack whose price is less than or equal to the current price.
For each popped entry, add its span to the current span. This is the key insight: when we pop (oldPrice, oldSpan), those oldSpan days are all <= oldPrice, which is <= current price. So they are all <= current price too, and their span should be absorbed into today's span.
After popping all smaller-or-equal entries, push (price, totalSpan) onto the stack. The stack remains monotonically decreasing because we only push after removing all entries that are <= the new price. The top of the stack is always the most recent price that was strictly greater.
Why Store Spans, Not Indices?
Storing (price, span) pairs instead of just prices lets us absorb multiple days in one pop. When we pop a day with span 5, we absorb all 5 of its days without needing to process them individually. This is what gives amortized O(1).
Step-by-Step Walkthrough
Prices: [100, 80, 60, 70, 60, 75, 85]. Stack starts empty. Day 1, price=100: stack empty, span=1. Push (100,1). Stack: [(100,1)]. Return 1.
Day 2, price=80: top is (100,1), 100 > 80, stop. span=1. Push (80,1). Stack: [(100,1),(80,1)]. Return 1. Day 3, price=60: top is (80,1), 80 > 60, stop. span=1. Push (60,1). Stack: [(100,1),(80,1),(60,1)]. Return 1.
Day 4, price=70: pop (60,1) since 60<=70, span=1+1=2. Top is (80,1), 80>70, stop. Push (70,2). Stack: [(100,1),(80,1),(70,2)]. Return 2. Day 5, price=60: top (70,2), 70>60, stop. span=1. Push (60,1). Day 6, price=75: pop (60,1) span=2, pop (70,2) span=4. Top (80,1), 80>75, stop. Push (75,4). Return 4. Day 7, price=85: pop (75,4) span=5, pop (80,1) span=6. Top (100,1), 100>85, stop. Push (85,6). Return 6.
Amortized Time Complexity
Each price is pushed onto the stack exactly once and popped at most once. Over n calls to next(), there are at most n pushes and n pops total. This gives O(2n) = O(n) total work, or amortized O(1) per call.
The worst case for a single call is O(n) — when the current price is higher than all previous prices, causing every stack entry to be popped. But this can only happen if those entries were pushed in previous calls, so the total pops across all calls is bounded by total pushes.
This amortized argument is the same one used in other monotonic stack problems. The key principle: each element participates in at most one push and one pop across its entire lifetime in the stack.
Stack Size After Processing
Notice the stack never grows beyond the number of strictly decreasing prices in the sequence. After processing all 7 prices, only (100,1) and (85,6) remain. The stack compresses the history by merging absorbed days.
Implementation in Python and Java
In Python, the stack is a list of tuples. The next method is concise: initialize span=1, while stack and stack[-1][0] <= price, pop and add span. Push (price, span). Return span. The __init__ method just creates an empty list.
In Java, use a Deque<int[]> (ArrayDeque of two-element arrays). The logic is identical. peek()[0] gives the top price. When popping, add peek()[1] to the running span. Push new int[]{price, span} after the while loop.
Both implementations use O(n) space for the stack in the worst case (strictly decreasing prices). In practice, the stack size is much smaller because entries get absorbed by higher prices.
YeetCode Flashcard Tip
Online Stock Span is a great design + monotonic stack combo problem. Practice it alongside Daily Temperatures and Next Greater Element on YeetCode to build fluency with stack-based streaming algorithms.
Complexity Summary
Time: amortized O(1) per next() call, O(n) total for n calls. Each element is pushed and popped at most once. The amortized constant is 2 (one push + one pop per element).
Space: O(n) worst case for the stack when all prices are strictly decreasing. In the best case (strictly increasing prices), the stack holds only one entry at any time because every previous entry gets popped.
The monotonic stack solution is optimal. Any solution must store enough information to answer future queries, and the stack stores exactly the minimal set of "unresolved" prices — those that could potentially be the first price greater than a future input.