Stock Span Problem Using Stacks

The stock span of a stock’s price on a given day is the maximum number of consecutive days (starting from today and going backward) for which the price was less than or equal to today’s price.

Problem Statement

Given an array of daily stock prices, compute the span for each day.

Prices: [100, 80, 60, 70, 60, 75, 85]
Spans:  [  1,  1,  1,  2,  1,  4,  6]

Day 5 (price 75): prices 60, 70, 60 are all ≤ 75, so span = 4. Day 6 (price 85): prices 75, 60, 70, 60, 80 are all ≤ 85, so span = 6.

Brute Force — O(n²)

For each day, look backward until you find a price greater than the current one:

def stock_span_brute(prices):
    """Time: O(n²), Space: O(n)"""
    n = len(prices)
    spans = [0] * n

    for i in range(n):
        span = 1
        j = i - 1
        while j >= 0 and prices[j] <= prices[i]:
            span += 1
            j -= 1
        spans[i] = span

    return spans

Stack-Based Solution — O(n)

Use a stack that stores indices of days with prices in decreasing order. For each new day, pop all days with smaller or equal prices — the span is the distance to the new stack top.

def stock_span(prices):
    """
    Calculate stock spans using a monotonic stack.
    Time: O(n), Space: O(n)
    """
    n = len(prices)
    spans = [0] * n
    stack = []  # Stack of indices, prices in decreasing order

    for i in range(n):
        # Pop all days with price <= current price
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()

        # Span = distance to previous greater element (or start)
        spans[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

    return spans

Trace

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

i=0, price=100: stack=[]       → span=1, stack=[0]
i=1, price=80:  stack=[0]      → span=1, stack=[0,1]
i=2, price=60:  stack=[0,1]    → span=1, stack=[0,1,2]
i=3, price=70:  pop 2(60)      → span=2, stack=[0,1,3]
i=4, price=60:  stack=[0,1,3]  → span=1, stack=[0,1,3,4]
i=5, price=75:  pop 4(60),3(70)→ span=4, stack=[0,1,5]
i=6, price=85:  pop 5(75),1(80)→ span=6, stack=[0,6]

Spans: [1, 1, 1, 2, 1, 4, 6]

Why O(n)?

Each index is pushed once and popped at most once. Total push operations = n, total pop operations ≤ n. So the total work is O(2n) = O(n).

Online Version (LeetCode 901)

The online version processes one price at a time:

class StockSpanner:
    def __init__(self):
        self.stack = []  # (price, span) pairs
    
    def next(self, price):
        """Time: O(1) amortized"""
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

Instead of storing indices, we store cumulative spans. When we pop an element, we absorb its span into the current day’s span.

Edge Cases

• Monotonically increasing — every day has span = i+1, stack always has one element
• Monotonically decreasing — every day has span = 1, stack grows to size n
• All same prices — last day has span = n
• Single day — span is always 1

When to Use This Pattern

The stock span is a special case of Previous Greater Element (PGE). Use this pattern whenever you need to find, for each element, how far back you can go before hitting a larger value. Common variations:

Related Problems

• Online Stock Span (LeetCode 901) — streaming version
• Next Greater Element I/II (LeetCode 496/503)
• Daily Temperatures (LeetCode 739)
• Largest Rectangle in Histogram (LeetCode 84)