Stock Span Problem

Stock Span Problem 

The Stock Span Problem is a financial problem where we have a series of daily price quotes for a stock and we need to calculate the span of the stock's price for each day. The span of the stock's price for a particular day is defined as the maximum number of consecutive days (including the current day) in which the price of the stock was less than or equal to the price on that day.

For example, consider the following list of stock prices: [100, 80, 60, 70, 60, 75, 85]

The corresponding stock spans would be: [1, 1, 1, 2, 1, 4, 6]

Explanation:

  • The span of the first day (100) is always 1 because there are no previous days to compare.
  • On the second day (80), the previous day's price was higher, so the span is 1.
  • On the third day (60), the previous day's price was higher, so the span is 1.
  • On the fourth day (70), the previous day's price (60) was lower, so the span is 2 (current day + previous day).
  • On the fifth day (60), the previous day's price was higher, so the span is 1.
  • On the sixth day (75), the previous day's price (60) was lower, so the span is 4 (current day + previous 3 days).
  • On the seventh day (85), the previous day's price (75) was lower, so the span is 6 (current day + all previous 5 days).

Solution Approach To solve the Stock Span Problem, we can use a stack to store the indices of the stock prices. We iterate through the given stock prices and for each price, we pop all the indices from the stack whose corresponding stock prices are less than or equal to the current price. The span of the current day is then calculated as the difference between the current day's index and the index of the top element in the stack. Finally, we push the current day's index onto the stack.

Now, let's solve the Stock Span Problem using this approach:

def calculate_stock_spans(prices):
    n = len(prices)
    spans = [0] * n  # to store the stock spans
    stack = []  # stack to store indices of prices
    # iterate through each price
    for i in range(n):
        # pop indices from the stack whose corresponding prices are less than or equal to the current price
        while stack and prices[i] >= prices[stack[-1]]:
            stack.pop()
        # calculate the span of the current day
        spans[i] = i - stack[-1] if stack else i + 1
        # push the current index onto the stack
        stack.append(i)
    return spans
# Test the solution
prices = [100, 80, 60, 70, 60, 75, 85]
spans = calculate_stock_spans(prices)
print("Stock Spans:", spans)  # Output: [1, 1, 1, 2, 1, 4, 6]

Explanation

  1. We define a function calculate_stock_spans that takes a list of stock prices as input and returns a list of stock spans.
  2. We initialize an empty stack and an empty list spans to store the stock spans.
  3. We iterate through each price in the given prices list using a loop.
  4. Inside the loop, we check if the stack is not empty and if the current price is greater than or equal to the price corresponding to the top index in the stack. If this condition is true, it means that the previous prices are smaller, so we pop the top index from the stack.
  5. After popping the indices from the stack, we calculate the span of the current day. If the stack is not empty, the span is the difference between the current day's index and the index of the top element in the stack. If the stack is empty, it means there are no previous days with prices greater than the current day, so the span is the current day's index plus 1.
  6. Finally, we push the current day's index onto the stack and repeat the process for the remaining prices.
  7. Once the loop is complete, we return the list of stock spans.
  8. We test the solution by passing the example list [100, 80, 60, 70, 60, 75, 85] to the calculate_stock_spans function and print the result.

Time Complexity The time complexity of this solution is O(n) because we iterate through the given prices list only once.

Space Complexity The space complexity is O(n) as well because we use the stack to store the indices, and in the worst case, the stack can contain all the indices if the prices are in descending order.

Next Post Previous Post