Loading problems...
TL;DR: The optimal solution uses a Monotonic Decreasing Stack to merge consecutive days of lower prices into a single span count, achieving amortized constant time complexity.
The Online Stock Span problem asks us to process a stream of daily stock prices. For each new price received, we must calculate its "span." The span is defined as the maximum number of consecutive days, ending with the current day, where the stock price was less than or equal to the current day's price.
This is a classic LeetCode 901 problem that tests your ability to handle data streams efficiently. A naive simulation would re-scan previous prices for every new entry, but the optimal approach requires identifying a specific structural property of the data.
The straightforward approach is to store every price received so far in a list. When next(price) is called, we iterate backward from the most recent price to the oldest. We maintain a counter and increment it as long as the historical prices are less than or equal to the current price. We stop immediately upon encountering a price strictly greater than the current one.
text
Class StockSpanner:
List prices
Function next(price):
prices.add(price)
span = 0
For i from prices.length - 1 down to 0:
If prices[i] <= price:
span = span + 1
Else:
Break
Return spanThe time complexity for a single call to next is , where is the number of calls made so far. In the worst-case scenario (e.g., a strictly decreasing sequence of prices like 100, 99, 98...), the algorithm scans only one element. However, if the prices are increasing, or we have a sequence like 50, 50, 50, ... 100, the algorithm rescans the entire history.
Over calls, the total time complexity becomes .
The constraints specify up to calls. While might pass for in some relaxed environments (approx operations), it is inefficient and prone to Time Limit Exceeded (TLE) errors on stricter platforms or larger test cases. More importantly, in an interview context, an solution for a stream processing problem is considered suboptimal.
The key intuition is that if a past price is smaller than or equal to today's price, it will never be the "stopping point" (the Previous Greater Element) for any future price.
Consider a sequence of prices: [60, 70, 80].
60 comes in, its span is 1.70 comes in, it is greater than 60. Any future price greater than 70 will automatically be greater than 60. Therefore, 60 becomes irrelevant as an individual data point; its weight (span of 1) is absorbed into 70.80 comes in, it absorbs 70 (which already includes 60).We can compress the history. Instead of storing every individual price, we store "blocks" or "intervals" of prices in a stack. Each element in the stack is a pair: {price, span}. The stack maintains the invariant that prices are strictly decreasing from bottom to top.
Visual Description: Imagine the prices as a skyline. A new building (current price) is constructed. If this new building is taller than the buildings immediately to its left, it "covers" or "hides" them. We collapse the hidden buildings into the new one, adding their widths (spans) to the new building's width. The stack represents the visible skyline of decreasing peaks that haven't been covered yet.

Let's trace the algorithm with the input prices: [100, 80, 60, 70, 60, 75, 85].
Input: 100
(100, 1).[(100, 1)]Input: 80
(100, 1). . No merge.(80, 1).[(100, 1), (80, 1)]Input: 60
(80, 1). . No merge.(60, 1).[(100, 1), (80, 1), (60, 1)]Input: 70
(60, 1). .(60, 1). Current span becomes .(80, 1). . Stop merging.Input: 60
(70, 2). . No merge.(60, 1).[(100, 1), (80, 1), (70, 2), (60, 1)]Input: 75
(60, 1). . Pop. Span: .(70, 2). . Pop. Span: .Input: 85
(75, 4). . Pop. Span: .(80, 1). . Pop. Span: .The correctness relies on the associative property of the span. The span of a price is .
When we pop an element because , we are asserting that the days covered by are also smaller than . Since was already the maximum of its own span range, and , it follows that is greater than or equal to all individual prices in that range. Thus, we can safely accumulate into the current span. The stack invariant (strictly decreasing prices) ensures we efficiently find the nearest preceding price strictly greater than without checking every single day.
cppclass StockSpanner { private: // Pair stores {price, span} stack<pair<int, int>> st; public: StockSpanner() { } int next(int price) { int span = 1; // Monotonic Stack: Pop elements that are less than or equal to current price // Accumulate their spans into the current span while (!st.empty() && st.top().first <= price) { span += st.top().second; st.pop(); } // Push current price and its calculated span st.push({price, span}); return span; } };
javaimport java.util.Stack; class StockSpanner { // Stack stores int arrays where: // index 0 is the price // index 1 is the span private Stack<int[]> stack; public StockSpanner() { stack = new Stack<>(); } public int next(int price) { int span = 1; // Monotonic Stack: Pop elements that are less than or equal to current price // Accumulate their spans into the current span while (!stack.isEmpty() && stack.peek()[0] <= price) { span += stack.peek()[1]; stack.pop(); } stack.push(new int[]{price, span}); return span; } }
pythonclass StockSpanner: def __init__(self): # Stack stores tuples of (price, span) self.stack = [] def next(self, price: int) -> int: span = 1 # Monotonic Stack: Pop elements that are less than or equal to current price # Accumulate their spans into the current span while self.stack and self.stack[-1][0] <= price: span += self.stack.pop()[1] self.stack.append((price, span)) return span
Time Complexity: Amortized
Although a single call to next might pop multiple elements (up to ), each element is pushed onto the stack exactly once and popped at most once. Over a sequence of calls, the total number of operations is proportional to . Therefore, the average time per operation is constant, .
Space Complexity:
In the worst case, if the input prices are strictly decreasing (e.g., 100, 99, 98...), no elements are ever popped. The stack will grow to size to store all price pairs.
The Monotonic Stack pattern used here is highly reusable for finding the "Next Greater" or "Previous Greater" element in an array.
The naive solution scans the history for every new price. If you have calls with prices in increasing order, the -th call scans items. The sum of operations is , which is too slow for the time limits.
(70, 2).[(100, 1), (80, 1), (70, 2)](80, 1). . Stop merging.(75, 4).[(100, 1), (80, 1), (75, 4)](100, 1). . Stop merging.(85, 6).[(100, 1), (85, 6)]A common mistake is storing only the price in the stack. If you only store the price, when you pop a smaller price, you lose the information about how many days that price covered. You must aggregate the history as you pop.
Yes, storing (price, index) is an alternative implementation of the same pattern. However, since this is an "online" problem (streaming data), calculating current_index - previous_greater_index requires maintaining a global index counter. Storing the span directly is often more intuitive for the specific requirement of "count consecutive days" and avoids index arithmetic errors.
If the stack becomes empty after popping, it means the current price is greater than all prices seen so far. The logic naturally handles this: the while loop terminates, and we push the current price with the accumulated span of the entire history plus one.