Online Stock Span

Medium

Bloomberg LP

1 view

Topics:

StacksArrays

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.

Online Stock Span

Medium

Bloomberg LP

1 view

Topics:

StacksArrays

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of calls to the `next` function we should expect?
Can the stock prices be negative or zero?
What data type should I use to store the stock prices? Are we concerned about floating-point precision issues?
Should the span calculation consider only the current price or the previous calculated spans as well?
Is there a maximum value for the stock prices?

Brute Force Solution

Approach

The brute force method for the online stock span problem involves, for each new stock price, looking back at all the previous prices. We want to find the number of consecutive days before and including the current day where the stock price was less than or equal to the current day's price.

Here's how the algorithm would work step-by-step:

When a new stock price comes in, we start by looking at all the days before it, one by one, in reverse order.
We check if the previous day's stock price is less than or equal to the current day's stock price.
If it is, we count that day and move to the day before that, checking again.
We keep going backwards and counting consecutive days until we find a day where the stock price was higher than the current day's price, or until we reach the beginning of the data.
The total number of consecutive days we counted, including the current day, is the span for the current day.
We then store this span for the current day and are ready for the next new stock price.

Code Implementation

class StockSpanner:

    def __init__(self):
        self.stock_prices = []

    def next(self, price):
        span = 1
        current_index = len(self.stock_prices)
        self.stock_prices.append(price)

        # Iterate backwards to find consecutive smaller prices
        for previous_index in range(current_index - 1, -1, -1):
            # Compare current price with previous prices
            if self.stock_prices[previous_index] <= price:
                span += 1
            else:
                # Stop when a larger price is found
                break

        return span

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach processes each new stock price individually. For each of the n prices, the algorithm iterates backwards through all previous prices to determine the span. In the worst-case scenario, for each of the n days, we might have to traverse all preceding days, resulting in roughly n * (n-1)/2 comparisons. Therefore, the time complexity is proportional to n², and we express it as O(n²).

Space Complexity

O(N) – The brute force approach described stores the span for each day. As new stock prices come in, the calculated span for each day is stored for future use. This means we are maintaining a collection of spans, one for each price we've processed. Therefore, the space used grows linearly with the number of stock prices, N, where N is the number of days for which stock prices are received, resulting in O(N) space complexity.

Optimal Solution

Approach

The key idea is to keep track of the relevant prices we've seen so far using a special tool. This tool helps us quickly find the most recent price that's bigger than the current price, so we can count how many consecutive days have a price less than or equal to the current day's price.

Here's how the algorithm would work step-by-step:

We'll use a tool (imagine a stack of papers) to remember prices and their spans (how many consecutive days are less than or equal to the current price).
When a new price comes in, we check our tool. If there are prices in the tool that are less than or equal to the current price, it means the current price 'covers' them and their spans get added to the span for this new price.
We keep removing these smaller or equal prices from the tool because they are no longer relevant for future calculations (they are 'covered' by the current price).
The moment we find a price in the tool that's bigger than the current price, or the tool is empty, we know the span for the current price. It's the number of prices we removed from the tool plus one (for the current day itself).
Finally, we add the current price and its calculated span to the tool, so it's available for the next price that comes in.

Code Implementation

class StockSpanner:

    def __init__(self):
        self.price_and_span_stack = []

    def next(self, price):
        span = 1
        # Pop prices from stack smaller or equal than current price
        while self.price_and_span_stack and self.price_and_span_stack[-1][0] <= price:
            span += self.price_and_span_stack[-1][1]
            self.price_and_span_stack.pop()

        # The current price and its span are added to the stack.
        self.price_and_span_stack.append((price, span))

        return span

# Your StockSpanner object will be instantiated and called as such:
# stock_spanner = StockSpanner()
# result1 = stock_spanner.next(price1)
# result2 = stock_spanner.next(price2)
# result3 = stock_spanner.next(price3)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the prices, using a stack to store price-span pairs. While the inner loop (removing smaller prices from the stack) might seem like it leads to O(n^2), each price is pushed onto the stack once and popped at most once. Therefore, across all calls to next(), the total number of push and pop operations is at most 2n. As a result, the amortized time complexity for each call to next() and thus for processing n prices is O(n).

Space Complexity

O(N) – The algorithm uses a stack to store prices and their corresponding spans. In the worst-case scenario, all prices could be monotonically increasing, meaning no prices are ever removed from the stack. Therefore, the stack could potentially store all N prices encountered so far, where N is the total number of prices received. This results in an auxiliary space requirement proportional to the input size. Hence, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input stream of stock prices	Initialize the data structure and return 0 for the first span query, or throw an exception depending on desired behavior.
Monotonically increasing stock prices	The stack will grow linearly, storing all previous prices, leading to a span equal to the current index plus one.
Monotonically decreasing stock prices	The span will always be 1 since no previous stock is less than or equal to the current price.
Large input stream causing stack overflow (memory limits)	The stack size should be monitored and potentially optimized using alternative data structures if memory becomes a constraint.
Integer overflow in stack operations or span calculation.	Use a data type with a larger range (e.g., long) for the stack and span calculations to prevent potential overflows.
Prices with large fluctuations	The stack will fluctuate in size as larger prices clear smaller prices, resulting in a mixed performance profile.
Zero or negative stock prices	The algorithm should work correctly as comparisons are based on relative price and the span is computed regardless of the specific price values as long as we can perform mathematical comparisons.
Prices at the maximum integer value for the given language	Carefully compare integers to prevent the stack and algorithm to work without integer overflow related issues.