algoadvance

You are given a series of daily price quotes for a stock, and you need to calculate the stock Span. The stock Span is defined as the number of consecutive days leading up to the current day for which the price of the stock was less than or equal to the price of the current day.

Implement the StockSpanner class:

• StockSpanner() Initializes the object of the class.
• int next(int price) Returns the span of the stock price given that day.

Clarifications Questions

1. Will the prices be given in sequence?
   • Yes, prices will be processed in the order they are received.
2. Are the prices always positive integers?
   • Yes, stock prices will always be positive integers.
3. Is there any upper limit to the number of days for which the stock prices will be provided?
   • No, the problem does not specify an upper limit, so the solution must handle a large number of days efficiently.

Strategy

We’ll use a stack data structure to maintain prices along with their spans. For each incoming price, we will:

1. Initialize the current span as 1.
2. Pop elements from the stack as long as the current price is greater than or equal to the top price of the stack. For each popped element, add its span to the current span.
3. Push the current price and its computed span onto the stack.
4. Return the computed span.

The stack will keep a tuple of (price, span). Each next() operation will have a time complexity of (O(n)) in the worst case, but amortized time complexity is (O(1)) due to each element being pushed and popped from the stack once.

Code

Here’s the implementation of the StockSpanner class:

class StockSpanner:

    def __init__(self):
        # Stack to store pairs of (price, span)
        self.stack = []

    def next(self, price: int) -> int:
        span = 1  # Initial span for the current price
        # Calculate span by popping all elements less than or equal to the current price
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        # Push the current price and its span onto the stack
        self.stack.append((price, span))
        return span


# Example usage:
# spanner = StockSpanner()
# print(spanner.next(100))  # Output: 1
# print(spanner.next(80))   # Output: 1
# print(spanner.next(60))   # Output: 1
# print(spanner.next(70))   # Output: 2
# print(spanner.next(60))   # Output: 1
# print(spanner.next(75))   # Output: 4
# print(spanner.next(85))   # Output: 6

Time Complexity

• Each element is pushed and popped from the stack at most once for each next() call.
• The amortized time complexity for each next() call is (O(1)).
• The space complexity is (O(n)) where (n) is the number of next() calls, as we are storing each price with its span in the stack.

This efficient use of stack ensures that we can calculate the span in constant amortized time, making it an optimal solution for this problem.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?