Stock Span Problem

The Stock Span Problem is a classic warm-up for the monotonic stack pattern. It asks a question that sounds like it needs nested loops, but a stack of indices answers it in a single pass.

The slow way first

The obvious idea: for each day i, walk backwards counting days while the price stays <= prices[i], and stop at the first taller day. That works, but in the worst case (prices going up forever) every day scans all the way to the start — O(n²).

The question to ask: while I count backwards, what am I really looking for? I am looking for the most recent day taller than today. Once I find it, the span is just the distance to it. If I could jump straight to that day instead of scanning, each step would be cheap.

The idea: a stack of taller days

Keep a stack of indices whose prices are strictly decreasing from bottom to top. The top is always the most recent day still taller than everything after it.

For each new day i, pop every index whose price is <= prices[i] — those days are shorter or equal, so they are swallowed into today's span and can never be the answer for any future day. After popping, the new top (if any) is the first taller day to the left, so the span is i - stack[-1]. If the stack is empty, every earlier day was shorter, so the span is i + 1. Finally push i.

The key insight: each index is pushed once and popped at most once, so the total work is O(n) even though any single day might pop several.

Walk through it

Step through the animation. The pointer i scans left to right. The stack on the right holds indices with decreasing prices. When i reaches day 5 (price 75), it pops days 4 and 3 (prices 60 and 70, both <= 75), lands on the taller day 1, and reads span 5 - 1 = 4. Day 6 (price 85) pops everything down to day 0 and gets span 6.

Pseudocode

span = array of zeros, same length as prices
stack = empty            # holds indices, prices strictly decreasing
for each index i in prices:
    while stack is not empty and prices[stack top] <= prices[i]:
        pop the stack
    if stack is empty:
        span[i] = i + 1                 # all earlier days were shorter
    else:
        span[i] = i - (stack top)       # reach back to the last taller day
    push i onto the stack
return span

The Python solution

def stock_span(prices):
    span = [0] * len(prices)
    stack = []                       # indices, prices decreasing
    for i in range(len(prices)):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return span

• stack holds indices, kept so their prices strictly decrease from bottom to top.
• The while loop pops every index whose price is <= prices[i] — those days fold into today's span.
• After popping, an empty stack means every earlier day was shorter, so span[i] = i + 1.
• Otherwise stack[-1] is the most recent taller day, and span[i] = i - stack[-1] is the distance back to just after it.
• We push i so later days can fold it in if it turns out shorter than them.

Complexity

Although one day can pop many indices, every index is pushed once and popped at most once across the whole run, so the amortized cost per day is constant. We trade O(n) extra space for the stack to go from O(n²) down to O(n).

When this pattern shows up

Practice