Course4all

Online Stock Span

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

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] 1. 100: Push (100, 1). Stack: [(100, 1)] 2. 80: Push (80, 1). Stack: [(100, 1), (80, 1)] 3. 70: Pop 60(1). Push (70, 2). Stack: [(100, 1), (80, 1), (70, 2)] 4. 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

priceActionStack StatusSpan Output
100Push[(100, 1)]1
80Push[(100, 1), (80, 1)]1
70Pop 60(1)[(100, 1), (80, 1), (70, 2)]2
85Pop 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.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionRemove All Adjacent Duplicates in String II
Next Question →Validate Stack Sequences