Day 25/60: The Online Stock Span and the Widget That Recounted Itself
60 Day DSA in JavaScript Challenge
I built a live stock-ticker widget. It shows one stock's price and, next to it, a number I call the span: how many consecutive trading days, counting today, the price has stayed less than or equal to today's value. Prices stream in one tick at a time, and on every tick the widget appended the new price and recomputed the span by scanning backward through history until it found a higher price.
It worked. It was also slow in a way that only showed up under load, which is the kind of slow I find hardest to spot.
The quadratic trap
The span asks: how far back can I go before I find a price strictly greater than today's? The naive answer counts backward one day at a time.
function spanByScan(prices) {
const spans = [];
for (let today = 0; today < prices.length; today++) {
let span = 1;
let i = today - 1;
while (i >= 0 && prices[i] <= prices[today]) {
span++;
i--;
}
spans.push(span);
}
return spans;
}
On a steadily rising market this is the worst case. Day t is greater than or equal to every earlier day, so the inner loop runs t times. Across the whole stream you pay 1 + 2 + ... + n, which is O(n^2). My widget was throwing away the answer it computed last tick and recounting the entire run from zero on the next one. Past a few thousand ticks it hitched on every update.
A decreasing monotonic stack of [price, span] pairs
The redundant part is the recounting. If yesterday's span already covered 40 days, today should be able to absorb that run whole rather than walking those 40 days again. So instead of storing individual days, I store collapsed runs as [price, span] pairs on a stack, kept strictly decreasing by price from bottom to top.
When a new price arrives, any pair on top whose price is at or below the new price can never block a future span again. So I pop it and fold its span into today's. Whatever price remains on top is the most recent day higher than today, which is exactly where the span stops.
Because the data is streaming, the natural shape is a class with a next(price) method that returns the span for that tick and keeps the stack alive between calls. That is the exact signature LeetCode 901 asks for.
class StockSpanner {
constructor() {
this.runs = []; // [price, span], strictly decreasing by price
}
next(price) {
let span = 1;
while (this.runs.length > 0 && this.runs[this.runs.length - 1][0] <= price) {
const [, poppedSpan] = this.runs.pop();
span += poppedSpan; // absorb the run we just beat
}
this.runs.push([price, span]);
return span;
}
}
const spanner = new StockSpanner();
const prices = [100, 80, 60, 70, 60, 75, 85];
console.log(prices.map((p) => spanner.next(p)));
// [1, 1, 1, 2, 1, 4, 6]
Tracing it by hand
100 -> span 1. 80 and 60 are each lower than what comes before, so each is its own run, span 1. Then 70 pops the 60 (span 1) and stops at 80: span 1 + 1 = 2. 60 again is a fresh low, span 1. Then 75 pops the 60 (1) and the 70 run (now span 2), stopping at 80: span 1 + 1 + 2 = 4. Finally 85 pops the 75 run (span 4) and the 80 (span 1), stopping at 100: span 1 + 4 + 1 = 6.
Notice how 75 absorbs the 70 run's span of 2 in a single pop. That is the work the naive version repeated and this version remembers.
Why it is amortized O(1) per tick
The analysis is easier if you stop looking at one call and look at the whole stream. Every price is pushed onto the stack exactly once. Once it is popped, it is gone forever, folded into a larger run. So across n calls to next, there are at most n pushes and at most n pops, total: 2n stack operations.
Any single next call might pop many entries and look expensive, but each of those entries was pushed by an earlier call that did its own O(1) push. Spread the 2n operations across the n calls and each call averages constant work. That is amortized O(1) per tick, O(n) for the whole stream, and the stack holds at most n pairs at any moment.
The strictly-decreasing invariant is what makes the popping correct. Every pair left on the stack has a higher price than everything above it, so the top is always the most recent day greater than today, which is the precise boundary the span stops at. Storing the span alongside the price means I never reopen a run I already summarized.
Two bugs I hit first
The first attempt pushed a bare price and tried to recover the span from runs.length. That breaks the moment two prices tie or the market dips and recovers, because length counts surviving runs, not the days inside them. The span has to ride along inside each pair.
The second was using < instead of <= in the pop condition. With a strict <, a day equal to a prior day stops the collapse one entry early, and the span comes back one short on flat stretches. Equal prices count toward the span, so the test must be <=.
Wrapping up
The widget was never wrong, just amnesiac. It recounted a run from scratch on every tick and paid O(t^2) for the privilege. The monotonic stack remembers runs by collapsing them into [price, span] pairs, and because each price is pushed and popped at most once, the streaming next(price) call is amortized O(1). Tomorrow I want to carry this discard-what-can-never-win-again instinct into a sliding-window maximum, where the stack becomes a deque.
Top comments (0)