Online Stock Span

Med

#0855Time: O(N) for each call to `next`, where N is the number of calls made so far. In the worst case (e.g., an increasing sequence of prices), the loop will run N times for the N-th call. The total time complexity for M calls is O(M^2).Space: O(N), where N is the number of calls made to `next`. We need to store all N prices in the list.1 company

Patterns

Design Data Stream

Data structures

Stack Monotonic Stack

Companies

INDmoney

Prompt

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.

For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.

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.

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 price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

Constraints:

1 <= price <= 10⁵
At most 10⁴ calls will be made to next.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves storing all the historical prices in a list. For each new price, we iterate backward through the list, counting how many consecutive days (including the current day) have a price less than or equal to the current day's price.

Algorithm

1. Initialize an empty list prices in the constructor.
1. In the next(price) method:
1. Add the new price to the prices list.
1. Initialize a counter span to 0.
1. Iterate backward from the end of the list (from index prices.size() - 1 down to 0).
1. For each price encountered, if it is less than or equal to the current price, increment span.
1. If a price is found that is greater than the current price, stop the iteration and break the loop.
1. Return the final span value.

Walkthrough

We maintain a java.util.ArrayList to store the sequence of prices received so far. The StockSpanner constructor initializes this list. In the next(int price) method, the new price is added to the end of the list. Then, we start a loop from the end of the list, moving backward. We count how many consecutive prices are less than or equal to the current day's price. The loop terminates as soon as we find a price that is greater than the current price, or when we have traversed the entire list. The final count is the span for the current day.

1import java.util.ArrayList;2import java.util.List;3 4class StockSpanner {5    private List<Integer> prices;6 7    public StockSpanner() {8        prices = new ArrayList<>();9    }10 11    public int next(int price) {12        prices.add(price);13        int span = 0;14        for (int i = prices.size() - 1; i >= 0; i--) {15            if (prices.get(i) <= price) {16                span++;17            } else {18                break;19            }20        }21        return span;22    }23}

Complexity

Time

O(N) for each call to `next`, where N is the number of calls made so far. In the worst case (e.g., an increasing sequence of prices), the loop will run N times for the N-th call. The total time complexity for M calls is O(M^2).

Space

O(N), where N is the number of calls made to `next`. We need to store all N prices in the list.

Trade-offs

Pros

Simple to understand and implement.
Requires only a basic list data structure.

Cons

Inefficient for a large number of calls. The time per call grows linearly with the number of prices seen, leading to a quadratic total time complexity (O(N^2) for N calls), which can be too slow for the given constraints.

This approach uses a monotonic stack to efficiently calculate the span. Instead of re-scanning all previous prices, we maintain a stack of pairs, where each pair consists of a price and its calculated span. The stack is kept in a monotonically decreasing order of prices (from bottom to top). This allows us to "skip" over consecutive days with smaller prices in constant time on average.

Algorithm

1. Initialize an empty stack stack in the constructor. The stack will store pairs of [price, span].
1. In the next(price) method:
1. Initialize currentSpan = 1 (for the current day's price).
1. While the stack is not empty and the price of the element at the top of the stack (stack.peek()[0]) is less than or equal to the current price:
1. Pop the element from the stack. Add its stored span (popped[1]) to currentSpan.
1. After the loop finishes, push a new pair [price, currentSpan] onto the stack.
1. Return currentSpan.

Walkthrough

The core idea is that the span of the current price is 1 (for the current day) plus the sum of the spans of all preceding consecutive days with prices less than or equal to the current price. We use a stack to store pairs of [price, span]. The stack will always maintain prices in a decreasing order.

When next(int price) is called:

We initialize the current span to 1.
We look at the top of the stack. As long as the stack is not empty and the price at the top is less than or equal to the current price, we pop from the stack.
For each element popped, we add its span to our current span. This is the key optimization: instead of counting one by one, we add the entire span of the smaller preceding element, effectively jumping over a block of days.
After the loop, we have the final span for the current price.
We then push the pair of (current price, calculated span) onto the stack to be used for future calculations. This maintains the monotonic property of the stack.

1import java.util.Stack;2 3class StockSpanner {4    private Stack<int[]> stack;5 6    public StockSpanner() {7        stack = new Stack<>();8    }9 10    public int next(int price) {11        int span = 1;12        while (!stack.isEmpty() && stack.peek()[0] <= price) {13            span += stack.pop()[1];14        }15        stack.push(new int[]{price, span});16        return span;17    }18}

Complexity

Time

Amortized O(1) for each call to `next`. While a single call can take up to O(N) time, each element is pushed and popped from the stack at most once over the entire sequence of N calls. Thus, the total time for N calls is O(N).

Space

O(N), where N is the number of calls made. In the worst case (a strictly decreasing sequence of prices), the stack will store an entry for each price.

Trade-offs

Pros

Highly efficient, with amortized constant time per operation.
Effectively handles large inputs without performance degradation.
Scales well as the number of calls increases.

Cons

Slightly more complex to conceptualize compared to the brute-force approach.
The space complexity is O(N) in the worst case, same as the brute-force approach.

Solutions

Solution

1class StockSpanner { private Deque < int []> stk = new ArrayDeque <>(); public StockSpanner () { } public int next ( int price ) { int cnt = 1 ; while (! stk . isEmpty () && stk . peek ()[ 0 ] <= price ) { cnt += stk . pop ()[ 1 ]; } stk . push ( new int [] { price , cnt }); return cnt ; } } /** * Your StockSpanner object will be instantiated and called as such: * StockSpanner obj = new StockSpanner(); * int param_1 = obj.next(price); */

1class StockSpanner { public: StockSpanner () { } int next ( int price ) { int cnt = 1 ; while ( ! stk . empty () && stk . top (). first <= price ) { cnt += stk . top (). second ; stk . pop (); } stk . emplace ( price , cnt ); return cnt ; } private: stack < pair < int , int >> stk ; }; /** * Your StockSpanner object will be instantiated and called as such: * StockSpanner* obj = new StockSpanner(); * int param_1 = obj->next(price); */

1class StockSpanner : def __init__ ( self ): self . stk = [] def next ( self , price : int ) -> int : cnt = 1 while self . stk and self . stk [ - 1 ][ 0 ] <= price : cnt += self . stk . pop ()[ 1 ] self . stk . append (( price , cnt )) return cnt # Your StockSpanner object will be instantiated and called as such: # obj = StockSpanner() # param_1 = obj.next(price)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem