Online Stock Span

Design an efficient algorithm using stacks to calculate the stock span for daily price quotes.

stack design monotonic stack data stream

Problem Statement

You are tasked with designing an algorithm that tracks daily stock price quotes and calculates the span for each price. The span of a stock's price for a given day is defined as the number of consecutive days (starting from the current day and moving backwards) on which the stock price was less than or equal to the current day's price.

You need to implement the StockSpanner class with a method next(int price), which accepts an integer price and returns the span of the stock's price for the current day. The function will be called several times with different price values.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 <= 105
At most 104 calls will be made to next.

Solution Approach

Stack-based Span Calculation

The key to solving this problem efficiently is using a stack to maintain the indices of prices in a monotonic decreasing order. For each price, we compare it with the top of the stack and pop from the stack while the current price is greater than or equal to the prices at those indices. The span for the current price is determined by the difference between the current index and the index of the last price that was greater than or equal to it.

Maintaining Monotonicity

By ensuring the stack remains in a monotonic decreasing order, we can efficiently find the number of consecutive days for which the price was less than or equal to the current price. Each element in the stack represents a price that was the largest among all previous prices for that day, helping us skip redundant comparisons and minimize time complexity.

Optimizing with O(1) Complexity

Each call to next() involves a constant number of operations. By maintaining a stack of prices, we reduce the need to traverse all previous days' prices, allowing us to calculate the span for each new price in O(1) average time complexity. This optimization ensures the solution scales efficiently with larger inputs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(1) per operation on average due to the stack's monotonic property, though in the worst case (if each price is strictly increasing), the time complexity can be O(n) for a series of calls. The space complexity is O(n), where n is the number of calls made to the next() function, as each price might be stored in the stack at once.

What Interviewers Usually Probe

Candidate understands the importance of using a stack for efficient state management.
Candidate demonstrates the ability to optimize a brute-force solution to O(1) complexity.
Candidate is able to articulate the trade-offs between time complexity and space complexity in stack-based problems.

Common Pitfalls or Variants

Common pitfalls

Not maintaining the stack in monotonic order, which can lead to incorrect span calculations.
Failing to efficiently handle the worst-case scenario where all stock prices are in increasing order.
Not fully utilizing the stack’s properties, such as avoiding redundant calculations for previously processed prices.

Follow-up variants

Implementing a solution with an alternative data structure (e.g., queue or array) for span calculation.
Handling the problem with multiple stock spans, each with separate stock price inputs.
Optimizing for a stream of data with real-time updates and dynamic span calculations.

FAQ

How do I calculate the stock span using a stack?

By maintaining a stack in monotonic decreasing order, you can calculate the span of a stock price by comparing it to the prices at the indices in the stack. The span for the current price is the difference between the current index and the index of the last price that was greater than or equal to it.

What is the time complexity of the solution?

The average time complexity is O(1) per operation due to the stack's efficient management. In the worst case, the time complexity can be O(n) if all prices are strictly increasing.

What does monotonic stack mean in the context of this problem?

A monotonic stack ensures that the prices in the stack are in a decreasing order. This property allows efficient span calculation by removing redundant comparisons for previously processed prices.

What other data structures could be used for the Online Stock Span problem?

While a stack is the most efficient data structure for this problem, alternatives such as arrays or queues could be used, but they would not offer the same performance, especially for larger inputs.

How does GhostInterview help with this problem?

GhostInterview provides guided solutions and practice problems that focus on stack-based state management, helping you master the techniques necessary for efficient problem-solving in coding interviews.

terminal

Solution

Solution 1: Monotonic Stack

Based on the problem description, we know that for the current day's price $price$, we start from this price and look backwards to find the first price that is larger than this price. The difference in indices $cnt$ between these two prices is the span of the current day's price.

class 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)

Continue Practicing

#1472 design browser history #895 maximum frequency stack #907 sum of subarray minimums