Typorithm · medium

Online Stock Span

online-stock-spanmonotonic-stackdecreasing-stackcollapse-spansstreaming

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Online Stock Span

Monotonic Stack

A decreasing stack of [price, span] pairs; today absorbs all not-greater days, summing their spans in O(1) amortized.

The span is how many consecutive prior days, up to today, had a price at or below today's.

A decreasing stack stores [price, span] pairs; today pops and absorbs every day with a price not exceeding it.

Folding in each popped span avoids recounting, giving amortized O(1) per call in a streaming setting.

Stack holds [price, span] pairs.

Absorb days with price <= today.

Sum their spans instead of recounting.

class StockSpanner {
  constructor() {
    this.stack = [];
  }

  next(price) {
    let span = 1;
    while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
      span += this.stack.pop()[1];
    }
    this.stack.push([price, span]);
    return span;
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Count today

Every price spans at least itself.

let span = 1

2. Absorb smaller days

Days with price <= today are subsumed by today's span.

while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {

3. Add their spans

Pop each absorbed day and fold in its precomputed span.

span += this.stack.pop()[1]

4. Store pair

Push the price with its computed span for future calls.

this.stack.push([price, span])

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.