Online Stock Span

medium stack monotonic design

Problem

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price. For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Inputprices = [100, 80, 60, 70, 60, 75, 85]

Output[1, 1, 1, 2, 1, 4, 6]

75 absorbs 60 (×2) and 70, span 4. 85 absorbs everything down to 100, span 6.

prices (comma-separated)

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

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

class StockSpanner {
    private Deque<int[]> stack = new ArrayDeque<>();
    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;
    }
}

class StockSpanner {
    stack<pair<int,int>> st;
public:
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second; st.pop();
        }
        st.push({ price, span });
        return span;
    }
};

Explanation

The span for today is how many consecutive recent days (including today) had a price less than or equal to today's. The clever part is that we never need to re-scan old days: a monotonic stack lets each new price absorb the spans of the days it dominates.

Each stack entry is a pair (price, span) — a price and how many days it already swallowed. For a new price, we start with span = 1 (today itself), then while the stack top's price is <= price, we pop it and add its span to ours, because all those days are also <= today's price.

After absorbing, we push (price, span) so future larger prices can absorb us in turn, and return span.

Example: prices 100, 80, 60, 70, 60, 75, 85. When 75 arrives it absorbs 60 (span 1), then 70 (which had already absorbed a 60, span 2), totaling 1 + 1 + 2 = 4. Then 85 absorbs everything back to (but not including) 100, giving span 6.

Because each price is pushed and popped at most once across all calls, the spans are computed in amortized constant time per day.

Time: amortised O(1) per call Space: O(n)