Online Stock Span Leetcode Problem 901 [Python Solution]

The span for our current price so we’ll add the current price along with its computed span to our stack.

This represents the current price and the maximum number of consecutive days, including today, where the stock price was less than or equal to the price of today.

Question

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.

Online Stock Span Leetcode Solution in Python

Implementing a Stock Spanner Algorithm

This “StockSpanner” class will efficiently calculate how many consecutive days a given stock price is less than or equal to the current day’s price.

How It Works

Let’s break down how this code works before we dive into the actual implementation:

1. Initialization

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

We start by initializing an empty stack, which will store pairs consisting of the stock price and its corresponding span.

2. The next Method

def next(self, price: int) -> int:

The heart of this class is the next method. It takes the current stock price as an input and returns the stock span, which is essentially the number of consecutive days before the current day when the stock price was less than or equal to the current day’s price.

3. Span Calculation

span = 1  # Initialize the span to 1 by default

We start by initializing the span to 1, as any stock price will always have a span of at least 1 day.

4. Iterating Through the Stack

# Check if we can increase the span by considering previous stock prices
while self.stack and self.stack[-1][0] <= price:
    span += self.stack.pop()[1]

Here, we iterate through the stack of stock prices and their corresponding spans. We compare the current price with the top of the stack. If the current price is greater, we pop the pair from the stack and add its span to the current span. We keep doing this until we find a stock price that’s greater than the current one.

5. Storing the Current Price and Span

# Add the current price and its span to the stack
self.stack.append((price, span))

After adjusting the span, we add the current price and its span to the stack. This is essential for the next calculation.

6. Returning the Span

return span

Finally, we return the calculated span, which represents the number of consecutive days the current stock price is less than or equal to its own value.

The Code

Here’s the complete Python code for the StockSpanner class:

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

    def next(self, price: int) -> int:
        span = 1  # Initialize the span to 1 by default

        # Check if we can increase the span by considering previous stock prices
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]

        # Add the current price and its span to the stack
        self.stack.append((price, span))

        return span

The StockSpanner class efficiently computes the span of stock prices using a stack data structure.

Example Usage of StockSpanner (Online Stock Span)

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

The example usage demonstrates its functionality.

Now, let’s dive into the time and space complexity analysis.

Time and Space Complexity

Time Complexity

The time complexity of this solution is O(N), where N is the number of elements (stock prices) processed using the next function.

In the worst case, each stock price is pushed and popped from the stack once, resulting in linear time complexity.

Space Complexity

The space complexity is also O(N), as we store the stock prices and their corresponding spans in the stack.

In the worst case, we may have to store all N stock prices in the stack, leading to linear space complexity.

Related Interview Questions By Company:

• Delete Node In A BST LeetCode
• Find K Closest Elements LeetCode
• Kth Largest Element In An Array LeetCode

Related Interview Questions By Difficulty:

• Implement Stack Using Queues LeetCode
• Remove All Adjacent Duplicates In String II LeetCode
• Asteroid Collision LeetCode

Related Interview Questions By Category:

• Valid Perfect Square LeetCode
• Last Stone Weight II LeetCode
• Ugly Number LeetCode

Conclusion

In this blog post, we addressed the Online Stock Span problem from LeetCode.

We designed an algorithm that efficiently computes the span of stock prices for each day based on the maximum number of consecutive days, starting from that day and going backward, where the stock price is less than or equal to the current day’s price.

We presented a Python solution using a stack data structure to maintain the necessary information.

Our solution has a time complexity of O(N) and a space complexity of O(N), making it efficient for processing a stream of stock prices.

If you have any questions, comments, or suggestions, please feel free to share them.

You can also find the original problem statement and test cases on LeetCode.

Happy coding!