Stock Spanner

Problem

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.

Examples

The brute-force approach

Store every price. For each new price, scan backward through stored prices until you find one larger than today's price. The span is the distance back to that previous larger price.

prices = []

def next(price):
    prices.append(price)
    span = 1
    i = len(prices) - 2   # start from yesterday
    while i >= 0 and prices[i] <= price:
        span += 1
        i -= 1
    return span

In the worst case (prices always increasing), every new day scans all previous prices. O(n) per query and O(n²) total over n queries. A monotonic stack collapses runs of consecutive non-dominant prices into a single stored entry, so each day is processed in amortized O(1).

Spotting the pattern

This is a Stack problem. The key question to ask yourself:

How do I count consecutive non-dominant days without scanning all the way back every time?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.