Online Stock Span

MEDIUM✓ CHIP-TIMEDLC #901 — FULL STATEMENT ↗

The drill: Feed a stock's daily price in one call at a time. Each call answers: how many consecutive days up to and including today has the price never been higher than today's?

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This drill feeds a stock's price one day at a time, one call per day, rather than handing over the whole history up front.

Each call passes today's price and expects back the span: the count of consecutive days ending today, including today itself, during which the price never rose above today's.

Spans build on whatever prices arrived in earlier calls — nothing about the future is known when a call is answered, and the sequence of calls always moves forward in time.

EX 01

StockSpanner()

next(100) → 1

next(80) → 1

next(60) → 1

next(70) → 2

next(60) → 1

next(75) → 4

next(85) → 6

A FALLING RUN, THEN A PARTIAL AND A FULL RECOVERY

EX 02

StockSpanner()

next(10) → 1

next(10) → 2

next(10) → 3

next(10) → 4

EQUAL PRICES KEEP EXTENDING THE SPAN

EX 03

StockSpanner()

next(5) → 1

next(4) → 1

next(3) → 1

next(2) → 1

next(1) → 1

STRICTLY FALLING — SPAN NEVER GROWS

the feed can run for tens of thousands of calls
prices are positive and can repeat across days
a span always counts today's own day
each call is answered using only prices seen so far

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Recomputing the span from scratch by walking every prior day is honest but wasteful — most of those prior days end up folded into today's same answer, so that work could be reused later.

HINT 2 THE STRUCTURE

A day's span already tells you how far back its own lower run extends. If the day right before you has a price no higher than yours, you can absorb its whole span in one step instead of re-walking every day inside it.

HINT 3 ONE STEP FROM THE ANSWER

Keep a stack of (price, span) pairs. Pop every entry whose price is at most today's, summing their spans as you go, then push (today's price, 1 + that sum) — the stack always holds a decreasing sequence of prices.

COACH'S BOARD — THE PATTERN, STEP BY STEP

ABSORB THE CALM STRETCHPATTERN · MONOTONIC PRICE STACKnext(100), next(80), next(60), next(70), next(60), next(75), next(85)

next 100

next 80

next 60

next 70

next 60

next 75

next 85

PRICE STACK (price:span)

— empty —

STEP 1

Each call absorbs every earlier day whose price it beats, summing their spans in one pop-loop instead of rewalking them.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/online-stock-span.py — RACE PACE

LANG ▸

PACE ▸

class StockSpanner:
    def __init__(self):
        self.stack = []  # (price, span)

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

TIME O(1) AMORTIZEDSPACE O(N)PYTHON · RACE PACE · 10 LN

class StockSpanner:
    def __init__(self):
        self.prices = []

    def next(self, price: int) -> int:
        self.prices.append(price)
        span = 0
        i = len(self.prices) - 1
        while i >= 0 and self.prices[i] <= price:
            span += 1
            i -= 1
        return span

TIME O(N) PER CALLSPACE O(N)PYTHON · TRAINING PACE · 12 LN

class StockSpanner {
    private final Deque<int[]> stack = new ArrayDeque<>(); // [price, span]

    public StockSpanner() {
    }

    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;
    }
}

TIME O(1) AMORTIZEDSPACE O(N)JAVA · RACE PACE · 15 LN

class StockSpanner {
    private final List<Integer> prices = new ArrayList<>();

    public StockSpanner() {
    }

    public int next(int price) {
        prices.add(price);
        int span = 0;
        int i = prices.size() - 1;
        while (i >= 0 && prices.get(i) <= price) {
            span++;
            i--;
        }
        return span;
    }
}

TIME O(N) PER CALLSPACE O(N)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED