Online Stock Span

Master this topic with zero to advance depth.

Online Stock Span

Calculate the 'span' of a stock's price today: the number of consecutive days (including today) the price was less than or equal to today's price.

Visual Representation

Prices: [100, 80, 60, 70, 60, 75, 85]

100: Push (100, 1). Stack: [(100, 1)]
80: Push (80, 1).  Stack: [(100, 1), (80, 1)]
70: Pop 60(1). Push (70, 2). Stack: [(100, 1), (80, 1), (70, 2)]
75: Pop 60(1), 70(2). Push (75, 4). Stack: [(100, 1), (80, 1), (75, 4)]

Medium

Examples

Input: ["StockSpanner","next","next","next","next","next","next","next"]\n[[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]

Approach 1

Level I: Brute Force (Linear Lookback per Query)

Intuition

For each new price, scan backwards through all previous prices and count consecutive days where price <= today's price. Stop as soon as a higher price is found.

⏱ O(N^2) across all calls💾 O(N)

java

import java.util.*;
class StockSpanner {
    private List<Integer> prices = new ArrayList<>();
    public int next(int price) {
        prices.add(price);
        int span = 1;
        for (int i = prices.size()-2; i >= 0; i--) {
            if (prices.get(i) <= price) span++;
            else break;
        }
        return span;
    }
    public static void main(String[] args) {
        StockSpanner ss = new StockSpanner();
        int[] p = {100, 80, 60, 70, 60, 75, 85};
        for (int x : p) System.out.print(ss.next(x) + " "); // 1 1 1 2 1 4 6
    }
}

Approach 2

Level III: Optimal (Monotonic Decreasing Stack)

Intuition

Use a stack to store pairs of (price, span). When a new price is added, pop all elements with price less than or equal to the current one, adding their spans to the current span before pushing it onto the stack.

⏱ O(1) amortized per next call💾 O(N)

Detailed Dry Run

price	Action	Stack Status	Span Output
100	Push	`[(100, 1)]`	1
80	Push	`[(100, 1), (80, 1)]`	1
70	Pop 60(1)	`[(100, 1), (80, 1), (70, 2)]`	2
85	Pop 75, 80	`[(100, 1), (85, 6)]`	6

java

import java.util.*;

class StockSpanner {
    Stack<int[]> stack = new Stack<>();
    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;
    }

    public static void main(String[] args) {
        StockSpanner ss = new StockSpanner();
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        for (int p : prices) System.out.print(ss.next(p) + " "); // 1 1 1 2 1 4 6 
    }
}

⚠️ Common Pitfalls & Tips

Be sure to store the accumulated span span += stack.pop()[1] so that the current element captures all smaller previous spans in constant time.

← Previous QuestionRemove All Adjacent Duplicates in String II

Next Question →Validate Stack Sequences

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.