Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Online Stock Span

MEDIUMProblemSolveExternal Links

Description

Design a data structure that collects daily stock prices one at a time and, for each new price, returns the span of that day's price.

The span on a given day is the maximum number of consecutive days ending on (and including) that day for which the stock price was less than or equal to today's price. In other words, starting from today and looking backward, count how many days in a row had a price that did not exceed today's price.

You need to implement the StockSpanner class:

  • StockSpanner() — Initializes the object.
  • int next(int price) — Accepts today's stock price and returns its span.

Examples

Example 1

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) → 1. No previous prices exist. The span is just today.
  • next(80) → 1. Yesterday's price was 100 which is greater than 80, so the span is only today.
  • next(60) → 1. Yesterday's price was 80 > 60, so span is 1.
  • next(70) → 2. Yesterday's price was 60 ≤ 70, but the day before that was 80 > 70. So the span covers today and yesterday: 2 consecutive days.
  • next(60) → 1. Yesterday's price was 70 > 60, so span is 1.
  • next(75) → 4. Looking backward: 60 ≤ 75, 70 ≤ 75, 60 ≤ 75, then 80 > 75. So the span covers 4 consecutive days (prices 75, 60, 70, 60).
  • next(85) → 6. Looking backward: 75 ≤ 85, 60 ≤ 85, 70 ≤ 85, 60 ≤ 85, 80 ≤ 85, then 100 > 85. So the span covers 6 consecutive days.

Example 2

Input:

["StockSpanner", "next", "next", "next", "next"]
[[], [10], [20], [30], [15]]

Output: [null, 1, 2, 3, 1]

Explanation:

  • next(10) → 1. First day, span is 1.
  • next(20) → 2. 10 ≤ 20, so span extends back through both days.
  • next(30) → 3. Both 20 and 10 are ≤ 30, so span covers all 3 days.
  • next(15) → 1. Yesterday's price 30 > 15, so span is only today.

Constraints

  • 1 ≤ price ≤ 10^5
  • At most 10^4 calls will be made to next

Editorial

Brute Force

Intuition

The most straightforward way to compute the span is to remember every price we have seen so far. Each time a new price arrives, we look backward through the stored prices and count how many consecutive ones are less than or equal to today's price.

Imagine you are standing at the end of a queue of people sorted by arrival time, each holding a sign showing their stock price. You turn around and walk backward, counting people whose signs show a price no higher than yours. The moment you see someone with a higher price, you stop counting. The number of people you counted (including yourself) is the span.

Step-by-Step Explanation

Let's trace through the calls: next(100), next(80), next(60), next(70), next(60), next(75), next(85).

Step 1: next(100). Prices so far: [100]. No previous prices to check. Span = 1.

Step 2: next(80). Prices: [100, 80]. Look back: prices[0] = 100 > 80 → stop. Span = 1.

Step 3: next(60). Prices: [100, 80, 60]. Look back: prices[1] = 80 > 60 → stop. Span = 1.

Step 4: next(70). Prices: [100, 80, 60, 70]. Look back: prices[2] = 60 ≤ 70 → count, prices[1] = 80 > 70 → stop. Span = 2.

Step 5: next(60). Prices: [100, 80, 60, 70, 60]. Look back: prices[3] = 70 > 60 → stop. Span = 1.

Step 6: next(75). Prices: [100, 80, 60, 70, 60, 75]. Look back: prices[4] = 60 ≤ 75 → count, prices[3] = 70 ≤ 75 → count, prices[2] = 60 ≤ 75 → count, prices[1] = 80 > 75 → stop. Span = 4.

Step 7: next(85). Prices: [100, 80, 60, 70, 60, 75, 85]. Look back: prices[5] = 75 ≤ 85 → count, prices[4] = 60 ≤ 85 → count, prices[3] = 70 ≤ 85 → count, prices[2] = 60 ≤ 85 → count, prices[1] = 80 ≤ 85 → count, prices[0] = 100 > 85 → stop. Span = 6.

Brute Force — Scanning Backward for Each Price — Watch how we store each new price and scan backward to count consecutive days with price ≤ today's price, stopping at the first higher price.

Algorithm

  1. Maintain a list prices to store all prices seen so far
  2. On each call to next(price):
    a. Append price to the list
    b. Initialize span = 1
    c. Walk backward from the previous index, incrementing span while the price at that index ≤ price
    d. Stop when a price greater than price is found or the beginning is reached
    e. Return span

Code

class StockSpanner {
private:
    vector<int> prices;
public:
    StockSpanner() {}
    
    int next(int price) {
        prices.push_back(price);
        int span = 1;
        int i = prices.size() - 2;
        
        while (i >= 0 && prices[i] <= price) {
            span++;
            i--;
        }
        
        return span;
    }
};
class StockSpanner:
    def __init__(self):
        self.prices = []
    
    def next(self, price: int) -> int:
        self.prices.append(price)
        span = 1
        i = len(self.prices) - 2
        
        while i >= 0 and self.prices[i] <= price:
            span += 1
            i -= 1
        
        return span
class StockSpanner {
    private List<Integer> prices;
    
    public StockSpanner() {
        prices = new ArrayList<>();
    }
    
    public int next(int price) {
        prices.add(price);
        int span = 1;
        int i = prices.size() - 2;
        
        while (i >= 0 && prices.get(i) <= price) {
            span++;
            i--;
        }
        
        return span;
    }
}

Complexity Analysis

Time Complexity: O(n) per call in the worst case, O(n²) total for n calls

Each call to next scans backward through up to all previous prices. If prices arrive in strictly increasing order (e.g., 1, 2, 3, ..., n), every call scans all previous entries. The total work across n calls is 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²).

Space Complexity: O(n)

We store every price in the list. After n calls, the list has n elements.

Why This Approach Is Not Efficient

The brute force approach rescans many of the same elements repeatedly. When a new high price arrives, it walks all the way back through prices we already determined were small.

The root issue is redundant comparisons: if we already know that prices at indices 3, 4, and 5 are all ≤ the price at index 5, and now a new price at index 6 is ≥ the price at index 5, we shouldn't need to individually re-check indices 3, 4, and 5 again. Their combined span should be carried forward.

With up to 10^4 calls and worst-case O(n) per call, total operations can reach ~5×10^7 — uncomfortably close to time limits. We need a way to skip over blocks of already-processed smaller prices.

Key insight: if we maintain a stack of "barrier" prices — those that are strictly larger than everything that came after them — we can jump directly to the previous barrier instead of scanning one element at a time. This is the monotonic stack pattern.

Optimal Approach - Monotonic Stack

Intuition

Instead of storing every individual price, we maintain a stack of (price, span) pairs. The stack is kept in decreasing order of prices — this is called a monotonic decreasing stack.

When a new price arrives, we pop all stack entries whose price is ≤ the new price. Each popped entry's span gets accumulated into the new entry's span because those days are now "absorbed" — the new price dominates them all. We then push the new (price, accumulated_span) pair.

Think of it like a series of buildings of different heights viewed from the right. A tall new building blocks the view of all shorter buildings behind it. Those shorter buildings become irrelevant — the new building's span absorbs them. Only buildings taller than the new one remain visible (stay on the stack).

The stack top always represents the most recent day whose price was strictly greater than all days that came after it. When computing the span, we simply pop entries with ≤ prices and add up their spans — no need to revisit individual days.

Step-by-Step Explanation

Let's trace through calls: next(100), next(80), next(60), next(70), next(60), next(75), next(85).

Stack stores (price, span) pairs. Bottom is leftmost.

Step 1: next(100). Stack is empty. No entries to pop. Span = 1. Push (100, 1).

  • Stack: [(100, 1)]

Step 2: next(80). Stack top = (100, 1). Is 100 ≤ 80? No. Span = 1. Push (80, 1).

  • Stack: [(100, 1), (80, 1)]

Step 3: next(60). Stack top = (80, 1). Is 80 ≤ 60? No. Span = 1. Push (60, 1).

  • Stack: [(100, 1), (80, 1), (60, 1)]

Step 4: next(70). Stack top = (60, 1). Is 60 ≤ 70? Yes → pop (60, 1), add span 1. Now span = 2. Stack top = (80, 1). Is 80 ≤ 70? No. Push (70, 2).

  • Stack: [(100, 1), (80, 1), (70, 2)]

Step 5: next(60). Stack top = (70, 2). Is 70 ≤ 60? No. Span = 1. Push (60, 1).

  • Stack: [(100, 1), (80, 1), (70, 2), (60, 1)]

Step 6: next(75). Stack top = (60, 1). Is 60 ≤ 75? Yes → pop, span = 2. Stack top = (70, 2). Is 70 ≤ 75? Yes → pop, span = 2 + 2 = 4. Stack top = (80, 1). Is 80 ≤ 75? No. Push (75, 4).

  • Stack: [(100, 1), (80, 1), (75, 4)]

Step 7: next(85). Stack top = (75, 4). Is 75 ≤ 85? Yes → pop, span = 5. Stack top = (80, 1). Is 80 ≤ 85? Yes → pop, span = 5 + 1 = 6. Stack top = (100, 1). Is 100 ≤ 85? No. Push (85, 6).

  • Stack: [(100, 1), (85, 6)]

Monotonic Stack — Absorbing Spans of Smaller Prices — Watch how each new price pops all stack entries with ≤ price, absorbing their spans. The stack stays in strictly decreasing order of prices.

Algorithm

  1. Initialize an empty stack of (price, span) pairs
  2. On each call to next(price):
    a. Set span = 1
    b. While the stack is not empty AND the top element's price ≤ price:
    • Pop the top element
    • Add its span to the current span
      c. Push (price, span) onto the stack
      d. Return span

Code

class StockSpanner {
private:
    // stack stores (price, span) pairs
    stack<pair<int, int>> st;
public:
    StockSpanner() {}
    
    int next(int price) {
        int span = 1;
        
        // Pop all entries with price <= current price
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        
        // Push current price with accumulated span
        st.push({price, span});
        return span;
    }
};
class StockSpanner:
    def __init__(self):
        # Stack stores (price, span) tuples
        self.stack = []
    
    def next(self, price: int) -> int:
        span = 1
        
        # Pop all entries with price <= current price
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack[-1][1]
            self.stack.pop()
        
        # Push current price with accumulated span
        self.stack.append((price, span))
        return span
class StockSpanner {
    // Stack stores [price, span] pairs
    private Deque<int[]> stack;
    
    public StockSpanner() {
        stack = new ArrayDeque<>();
    }
    
    public int next(int price) {
        int span = 1;
        
        // Pop all entries with price <= current price
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.peek()[1];
            stack.pop();
        }
        
        // Push current price with accumulated span
        stack.push(new int[]{price, span});
        return span;
    }
}

Complexity Analysis

Time Complexity: O(1) amortized per call, O(n) total for n calls

Each price is pushed onto the stack exactly once and popped at most once across all calls. Even though a single call might pop multiple elements, the total number of push and pop operations across all n calls is at most 2n. This gives an amortized cost of O(1) per call.

Space Complexity: O(n) worst case

In the worst case (strictly decreasing prices, e.g., 100, 90, 80, ...), nothing ever gets popped, and the stack grows to hold n entries. However, in practice the stack size is usually much smaller because higher prices absorb older entries.