Design a class that receives a daily stock price and returns the span: the number of consecutive days (going backward from today) with a price less than or equal to today's price.

Engineering takeaway. This is the classic monotonic stack, and it's everywhere in real code — think "next smaller element", histogram area, or maintaining running maxima as new data arrives. The stack stays sorted by price, and every element is pushed and popped at most once, which is why the amortized cost is O(1) per call.

Intuition

next(price) asks: how far back do I need to go before I hit a price strictly greater than today's?

That immediately suggests a stack of prices in decreasing order. When a new price arrives, pop every entry with price <= today — each popped entry's span is absorbed into today's. The remaining top of the stack is the first greater price.

Rather than storing just prices, store pairs of (price, span) so the span travels with its price.

Approach

  1. Stack holds [price, span] pairs, prices strictly decreasing from bottom to top.
  2. For each next(price):
    • start span = 1;
    • while the top price <= price, pop it and add its span;
    • push [price, span] and return it.
class StockSpanner {
  private stack: Array<[number, number]> = [];
 
  next(price: number): number {
    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;
  }
}

Each price is pushed once and popped at most once, so even though an individual next() can pop many entries, the total work across all calls is O(n).

Complexity

  • Time: O(1) amortized per next().
  • Space: O(n) for the stack.

The lesson

"Look backwards until a condition stops holding" + "data arrives one at a time" = monotonic stack. The trick to remember: store the aggregated answer (span) with the value, not in a separate map — it keeps the running computation self-contained and the code short.