Log inSign up
mediumLeetCodeNot Started

Online Stock Span

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

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 backward) for which the stock price was less than or equal to the price of that day.

* For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days. * Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.

Implement the StockSpanner class: * StockSpanner() Initializes the object of the class. * int next(int price) Returns the span of the stock's price given that today's price is price.

Example 1 · Standard Stream Simulation:

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: 100 -> 1. 80 -> 1. 60 -> 1. 70 absorbs 60 -> span 2. 60 -> 1. 75 absorbs 60 and 70 (span 1+1+2=4). 85 absorbs 75, 60, 70, 60, 80 -> span 6.

Constraints:

  • 1 <= price <= 105
  • At most 104 calls will be made to next.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Learn how to compress consecutive history by storing aggregated weights (price, span) in stack frames.
  • Understand why each day's price quote is pushed and popped at most once, providing amortized O(1) time per query.
  • Handle online streaming constraints where future elements are unknown.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Store (price, span) pairs in a monotonic decreasing stack.
  • When next(price) is called, start with span = 1.
  • While !st.empty() && st.top().price <= price, pop st.top() and accumulate span += popped.span.
  • Push (price, span) and return span.

Connected Patterns:

Daily TemperaturesNext Greater Element ILargest Rectangle in Histogram

1. List History Backward Scan

Intuition

Append each incoming price to a list, then loop backward from the end and count consecutive prices <= current price.

Algorithm

  1. Step 1: Append price to history list prices.
  2. Step 2: Initialize span = 0.
  3. Step 3: Loop backward from prices.length - 1 down to 0.
  4. Step 4: If prices[i] <= price, increment span. Otherwise, break.
  5. Step 5: Return span.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class StockSpanner {
5 std::vector<int> prices;
6public:
7 StockSpanner() {}
8
9 int next(int price) {
10 prices.push_back(price);
11 int span = 0;
12 for (int i = (int)prices.size() - 1; i >= 0; i--) {
13 if (prices[i] <= price) {
14 span++;
15 } else {
16 break;
17 }
18 }
19 return span;
20 }
21};
22
23int main() {
24 StockSpanner spanner;
25 std::vector<int> stream = {100, 80, 60, 70, 60, 75, 85};
26 std::cout << "Spans: ";
27 for (int p : stream) {
28 std::cout << spanner.next(p) << " ";
29 }
30 std::cout << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) per call, O(N^2) total — On the N-th day, scanning backward through all previous prices takes O(N) operations in the worst case.
  • Space complexity: O(N) — O(N) space to store all previous prices in a dynamic list.

Why Brute Force Doesn't Scale:

For 10,000 calls in increasing order, brute force performs ~5 * 107 operations.

Monotonic Stack handles 10,000 queries in <5ms.

2. Index-Based Monotonic Stack

Intuition

Track an incrementing day counter dayIndex. The span is simply dayIndex - prevGreaterDayIndex.

Algorithm

  1. Step 1: Maintain a day counter day = 0 and stack of pairs (price, day).
  2. Step 2: On next(price), pop elements while stack.top().price <= price.
  3. Step 3: span = stack.empty() ? (day + 1) : (day - stack.top().day).
  4. Step 4: Push (price, day) and increment day++.
  5. Step 5: Return span.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class StockSpanner {
6 std::stack<std::pair<int, int>> st; // price, day
7 int day;
8public:
9 StockSpanner() : day(0) {}
10
11 int next(int price) {
12 while (!st.empty() && st.top().first <= price) {
13 st.pop();
14 }
15 int span = st.empty() ? (day + 1) : (day - st.top().second);
16 st.push({price, day});
17 day++;
18 return span;
19 }
20};
21
22int main() {
23 StockSpanner spanner;
24 std::vector<int> stream = {100, 80, 60, 70, 60, 75, 85};
25 std::cout << "Spans: ";
26 for (int p : stream) std::cout << spanner.next(p) << " ";
27 std::cout << std::endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(1) Amortized — Store (price, dayIndex) on monotonic stack. Span is computed directly as dayIndex - prevIndex.
  • Space complexity: O(N) — O(N) stack storage.

3. Optimal Monotonic Stack with Span Compression

Intuition

Store (price, span) pairs directly. When a new price arrives, pop all smaller or equal elements and add their accumulated spans together. This compresses history into a single stack frame.

Algorithm

  1. Step 1: Initialize an empty stack st storing pairs of (price, span).
  2. Step 2: Inside next(price), initialize span = 1.
  3. Step 3: While st is non-empty and st.top().price <= price, add st.top().span to span and pop st.
  4. Step 4: Push (price, span) onto st.
  5. Step 5: Return span.

Span Aggregation Execution Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
Current operationSTEP 1 OF 7
Return 1
Visual state
Values and pointers at this exact step
stack
This stack trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Return 1.

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class StockSpanner {
6 std::stack<std::pair<int, int>> st; // {price, span}
7public:
8 StockSpanner() {}
9
10 int next(int price) {
11 int span = 1;
12 while (!st.empty() && st.top().first <= price) {
13 span += st.top().second;
14 st.pop();
15 }
16 st.push({price, span});
17 return span;
18 }
19};
20
21int main() {
22 StockSpanner spanner;
23 std::vector<int> stream = {100, 80, 60, 70, 60, 75, 85};
24 std::cout << "Spans: ";
25 for (int p : stream) {
26 std::cout << spanner.next(p) << " ";
27 }
28 std::cout << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(1) Amortized — Each price is pushed onto the stack exactly once and popped at most once across all next() calls. Amortized O(1) per query.
  • Space complexity: O(N) — O(N) auxiliary space in the worst case of strictly decreasing prices.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.List History Backward ScanO(N) per query, O(N^2) totalO(N)Append to dynamic list and scan backwards on each query.Re-scanning every past price on every call.
2.Index-Based Monotonic StackO(1) AmortizedO(N)Store price and absolute day index; span is currentDay - prevGreaterDay.None.
3.Optimal Monotonic Stack with Span CompressionOptimalO(1) AmortizedO(N)Store (price, span) and accumulate spans upon popping.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using < instead of <= when popping (forgetting that equal prices count towards today's span).

Pitfall 2:

Initializing span = 0 instead of span = 1 (today itself always counts as 1 day).

Pitfall 3:

Storing full history and rescanning on each call.

Crucial Edge Cases to Validate:

  • Strictly increasing price stream (e.g. `10, 20, 30, 40`) — Each call pops the entire stack; spans are [1, 2, 3, 4].
  • Strictly decreasing price stream (e.g. `50, 40, 30, 20`) — No elements are popped; spans are [1, 1, 1, 1].
  • All equal prices (e.g. `25, 25, 25, 25`) — Since condition is <=, previous equal prices are absorbed; spans are [1, 2, 3, 4].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether equal prices are included in the span (LeetCode definition: less than OR equal to).
  2. Explain the span compression technique: instead of re-iterating over 1,000 preceding smaller days, their combined span is stored as a single integer.
  3. Derive the amortized O(1) complexity via the aggregate method.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the amortized time complexity of StockSpanner.next() O(1)?

2.What is stored in each stack frame in the optimal approach?

Back to DSA Sheet