Skip to main content

901. Online Stock Span

medium

Stream stock prices and report each day's 'span' — how many consecutive prior days were at most today's price. A streaming twist on the monotonic-stack pattern.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design an algorithm that 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 in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day. Implement the StockSpanner class: StockSpanner() Initializes the object of the class. int next(int price) Returns the span of the stock's price given that today's price is price.

Constraints

  • 1 <= price <= 10^5
  • At most 10^4 calls will be made to next.

Examples

Example 1

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation: StockSpanner stockSpanner = new StockSpanner(); stockSpanner.next(100); // return 1 stockSpanner.next(80); // return 1 stockSpanner.next(60); // return 1 stockSpanner.next(70); // return 2 stockSpanner.next(60); // return 1 stockSpanner.next(75); // return 4, because the last 4 prices (including today's 75) were less than or equal to today's price. stockSpanner.next(85); // return 6

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive: scan backward every call. That's O(n^2) total across all calls.

Hint 2

Notice: if a prior day's price is lower than today's, we'll never need its individual span again — we can collapse it into today's.

Hint 3

Keep a monotonic decreasing stack of (price, span) pairs. While the top's price <= current price, pop and absorb its span.

Hint 4

Today's answer is 1 + sum of absorbed spans. Push (price, answer) before returning.

Solution approach

Reveal approach

Monotonic decreasing stack of (price, span) pairs. On next(price): start with span = 1. While stack is non-empty and stack.top().price <= price, pop and add the popped span to your running span. Push (price, span) and return span. Each price is pushed and popped at most once across the lifetime of the data structure, so amortized O(1) per call and O(n) space. The 'collapse spans into the current day' trick is the lesson here — it's the same idea behind histogram-area problems.

Complexity

Time
Amortized O(1) per call
Space
O(n)

Related patterns

  • stack
  • monotonic-stack
  • design

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Online Stock Span and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →