This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#901) before relying on it.

Online Stock Span

See how a monotonic decreasing stack efficiently calculates the span of stock prices — consecutive days where price was less than or equal to today's.

Monotonic Stack LeetCode 901 ↗ Medium

The Problem

Design an algorithm that collects daily price quotes for a stock and returns the span of that stock's price for the current day. The span is the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today's price.

Example: For prices [100, 80, 60, 70, 60, 75, 85], the spans are [1, 1, 1, 2, 1, 4, 6]. On day 6 (price 85), the span is 6 because prices on days 1–5 (80, 60, 70, 60, 75) are all ≤ 85, and day 0 (100) is not.

The key insight is that a monotonic decreasing stack storing (price, span) pairs lets us absorb the spans of all popped entries, giving O(n) amortized time.

Interactive Visualization

Prices (comma-separated)

Preset

Speed:

Current Day

Price

Span

Stack Size

Stock Prices & Spans

Stack (price, span) — decreasing order

Stack is empty

Code

fun stockSpan(prices: IntArray): IntArray {    val stack = ArrayDeque<Pair<Int, Int>>()  // (price, span)    val result = mutableListOf<Int>()    for (price in prices) {        var span = 1        while (stack.isNotEmpty() && stack.last().first <= price)            span += stack.removeLast().second        stack.addLast(Pair(price, span))        result.add(span)    }    return result.toIntArray()}

def stockSpan(prices):    stack = []  # (price, span)    result = []    for price in prices:        span = 1        while stack and stack[-1][0] <= price:            span += stack.pop()[1]        stack.append((price, span))        result.append(span)    return result

Status & Log

Press Step or Play to begin.

How It Works

Key Insight

The stack stores (price, span) pairs in strictly decreasing order of price. When a new price arrives that is greater than or equal to the stack top, we pop entries and absorb their spans into the current span. This works because if today's price dominates a previous entry, it also dominates everything that entry already dominated.

Algorithm Steps

Initialize: Start with an empty stack and span = 1 for each new price (it always counts itself).
Pop loop: While the stack is non-empty and the top price ≤ current price, pop (topPrice, topSpan) and add topSpan to the current span. The popped entry's entire span is absorbed.
Push: Push (price, span) onto the stack. The stack remains in decreasing order because the current price is strictly less than whatever is now on top (or the stack is empty).
Result: The accumulated span is the answer for this day.

Why Monotonic?

After each push, the stack prices are strictly decreasing from bottom to top. A new price that is large enough pops all smaller-or-equal entries, absorbing their spans. This is what makes the stack "monotonic decreasing." Each element is pushed and popped at most once, giving amortized O(1) per next() call.

Complexity

Time O(n) amortized

Space O(n)

Each price is pushed onto the stack exactly once and popped at most once across all next() calls. So the total work across n calls is O(n), giving O(1) amortized per call. The stack can hold at most n elements (when prices are strictly decreasing), so space is O(n).