Online Stock Span LeetCode 901 Guide

LeetCode 901 — Online Stock Span — asks you to design a StockSpanner class with a single method next(price) that accepts daily stock prices one at a time and returns the span for that day. The span is defined as the maximum number of consecutive days (including today) for which the stock price was less than or equal to today's price. The key word is "online" — prices arrive one at a time and you must respond immediately without looking ahead.

For example, if prices arrive in the sequence [100, 80, 60, 70, 60, 75, 85], the returned spans are [1, 1, 1, 2, 1, 4, 6]. The span of 85 is 6 because all six preceding prices (100 excluded, so actually looking back: 75, 60, 70, 60, 80 are all <= 85, and 100 > 85 stops the count) — wait, tracing carefully: 85 is >= 75, 60, 70, 60, 80 (all five before it) but 100 > 85, so span = 6 including today. The span of 75 is 4 because 75 >= 60, 70, 60 but 80 > 75.

LeetCode 901 is rated Medium and is a direct application of the monotonic stack span-counting pattern. A naive approach rescans previous days on every call, giving O(n) per call and O(n^2) total for n calls. The optimal solution uses a monotonic decreasing stack of (price, span) pairs to achieve O(1) amortized per call by accumulating spans at push time rather than rescanning.

The brute force approach stores all prices seen so far in a list. On each call to next(price), you append the new price then scan backwards from the second-to-last element, counting days while the price is <= the current price. You stop as soon as you find a day where the price is strictly greater. The span is the count plus one (for today itself).

This approach is correct and straightforward. Its time complexity is O(n) per call in the worst case, where n is the number of prices seen so far. For a monotonically decreasing sequence — each price smaller than the last — every call scans the entire history. After 10,000 calls that is up to 50 million comparisons, which may time out. Space is O(n) for the stored price history.

The worst-case input for brute force is a strictly increasing sequence — each new price is the largest seen so far, so the backward scan must traverse the entire history every time. The brute force is useful for understanding correctness but is replaced by the monotonic stack approach for performance. The key observation is that when a smaller price is popped from the stack, its span already captures all the days it previously absorbed — there is no need to revisit them.

The optimal solution maintains a stack of (price, span) pairs in monotonic decreasing order by price. The invariant is that prices from bottom to top are strictly decreasing. Each pair encodes not just the price itself but the number of days (including the day of that price) that were absorbed into it when it was first pushed.

When next(price) is called, initialize a running span accumulator at 1 (counting today). Then enter a while loop: while the stack is non-empty and the top pair's price is <= the current price, pop the pair and add its span to the accumulator. After the loop, push (price, accumulator) onto the stack and return the accumulator as the span.

The stack maintains the decreasing invariant because we pop all prices <= the current before pushing. Any price that survives on the stack is strictly greater than the current price, so the new entry is the smallest price on the stack after the push. The span stored with each entry correctly represents all consecutive days up to that price where prices were <= that price's value — a compressed but complete record of history.

When a (price, span) pair is popped because its price is <= the current price, that popped price's span tells you how many consecutive prior days (including the popped day itself) had prices <= the popped price. Since the popped price is itself <= the current price, all those days also have prices <= the current price by transitivity. Adding the popped span to the accumulator correctly counts all those days without revisiting them.

This is the fundamental insight: the span on each stack entry is a compressed count of days already verified to be <= that entry's price. When that entry is popped because the current price dominates it, its days automatically belong to the current price's span. No re-scanning is needed because the work was already done when the popped entry was first pushed.

Without span accumulation, you would need to re-examine each individual day. With span accumulation, an entry like (75, 4) means "75 and the 3 days before it all had prices <= 75." If a new price of 85 arrives, popping this entry and adding 4 to the accumulator captures all four days in a single O(1) operation — regardless of how many individual prices those four days represent.

Trace prices [100, 80, 60, 70, 60, 75, 85] through the algorithm. At each step we show the incoming price, the stack state before and after, and the returned span. The stack holds (price, span) pairs; top of stack is on the right.

After processing all seven prices, the spans returned are [1, 1, 1, 2, 1, 4, 6]. The final stack contains only (100, 1) and (85, 6) because 85 absorbed everything between them. The entry (85, 6) encodes that 85 and the five days before it (75, 60, 70, 60, 80) all had prices <= 85 — six days total. The entry (100, 1) survives because 100 > 85 and was never popped.

Notice how price 85 popped four entries in a single call: (75, 4), (80, 1) — wait, let us retrace carefully. After price 75 the stack is [(100,1),(80,1),(75,4)]. When 85 arrives: pop (75,4) → span=5, pop (80,1) → span=6, top is (100,1) and 100 > 85 so stop. Push (85,6). The span 4 stored with 75 already compressed 60, 70, 60, 75 — four days. Popping it in one step saved three comparisons.

Python solution: class StockSpanner: def __init__(self): self.stack = [] # list of (price, span) tuples def next(self, price: int) -> int: span = 1; while self.stack and self.stack[-1][0] <= price: span += self.stack.pop()[1]; self.stack.append((price, span)); return span. The stack is a list of tuples. The while loop pops all pairs with price <= current and accumulates their spans. After the loop, append (price, span) and return span. Time is O(1) amortized per call; space is O(n) where n is total calls.

Java solution: class StockSpanner { private Deque<int[]> stack; public StockSpanner() { stack = new ArrayDeque<>(); } public int next(int price) { int span = 1; while (!stack.isEmpty() && stack.peek()[0] <= price) { span += stack.pop()[1]; } stack.push(new int[]{price, span}); return span; } }. Java uses int[] arrays of length 2 as pairs and ArrayDeque as the stack. Deque.push() and Deque.peek() operate on the front (top). The logic is identical to Python.

Both solutions share the same core: initialize span to 1, pop-and-accumulate in a while loop, push the new pair, return span. The stack size is bounded by the number of prices that have not yet been dominated by a larger price — in the worst case (decreasing sequence) all prices remain on the stack, giving O(n) space for n calls total. For an increasing sequence, the stack holds only one entry at a time.

Daily Temperatures (LeetCode 739) is the closest relative: instead of counting span, you compute the number of days until the next strictly warmer temperature. Both use a monotonic decreasing stack and process one element at a time, but Daily Temperatures stores indices (to compute day differences) while Online Stock Span stores (price, span) pairs (to accumulate counts). Mastering one makes the other straightforward.

Car Fleet (LeetCode 853) uses a different flavor of the monotonic stack pattern: sort cars by position, compute arrival times, and use a stack to count how many fleets form. Largest Rectangle in Histogram (LeetCode 84) uses a monotonic increasing stack with index arithmetic to compute maximum rectangle areas. Next Greater Element (LeetCode 496, 503) is a direct variant where the stack returns the next greater value rather than counting days.

The online stock span family — problems that require accumulating counts as you scan — also includes problems like sum of subarray minimums (LeetCode 907) and number of visible people in a queue (LeetCode 1944). In all of these, the stack stores compressed representations of history rather than raw indices, enabling O(1) amortized responses to online queries. Once you internalize the (value, count) pair pattern from LeetCode 901, these harder variants become much more approachable.