Master the Stock Span Problem by 3 Easy Steps in Python

Welcome to our guide on mastering the Stock Span Problem. Learn to Calculate Stock Span using the Stock Span Algorithm and Stock Span Python Implementation.

In intermediate-level interviews, candidates are often asked to solve problems related to stock prices, such as the Stock Span Problem. The challenge involves calculating the span of stock prices for a series of days, which is a measure of how many consecutive days the price of a stock has been less than or equal to its price on the current day.

Join the discussion on Reddit about the Stock Span Problem and connect with people preparing for interviews.

FREE Offer: If you’re a new visitor preparing for an interview and need help, you can use the form on the right side to ask your question. It’s free and doesn’t require signing in. Alternatively, you can ask in our Quora space, which is also free, and you’ll receive a response within 24 hours. Go ahead and check it out! Don’t miss our top tips on Understanding object oriented programming oop in cpp , reverse a linked list recursively and Function Overloading in C++. Your dream job is just a click away!

Understand the Stock Span Problem

Ready to learn a new algorithm? I hope your interviews are going well. Let’s begin with the crucial first step: understanding what stock span means.

In the Stock Span Problem, you are given an array of daily stock prices. The span of a stock’s price on a given day is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

Feeling confused? Don’t worry, below I have provided a real-world example to explain how the stock span algorithm works.

Real-World Example of Stock Span Algorithm

Suppose we have an array of prices for 7 days: [100, 80, 60, 70, 60, 75, 85]. The output spans should be [1, 1, 1, 2, 1, 4, 6].

Have you grasped the input array and what the interview expects from you in solving the stock span problem? Now, let’s break down each step sequentially to enhance understanding.

For 100: There are no previous days with a price higher than 100, so the span is 1.
For 80: There are no previous days with a price higher than 80, so the span is 1.
For 60: There are no previous days with a price higher than 60, so the span is 1.
For 70: The price on the previous day (60) is less than 70, so the span is 2.
For 60: There are no previous days with a price higher than 60, so the span is 1.
For 75: The prices on the previous days (60, 70, and 60) are all less than 75, so the span is 4.
For 85: The prices on all previous days (80, 60, 70, 60, and 75) are all less than 85, so the span is 6.

In other words, we have compare previous each elements with less then and equal to. which means if we have 80,70,60,60,75 therefore we have total 5 span and just because we compare with equal to so we increase it by 1.

Let implement that logic For 75. in this case we have 60,70 and 60 which means 3 span and just because we have equal to we have increase it by 1.

I hope you can understand how the stock span algorithm works. Don’t worry if you still have questions; you will grasp its logic in the next section where I am going to solve the stock span problem using a stack.

Understand the Logic Behind the Stock Span Calculation

To solve the Stock Span problem efficiently, we can utilise a stack. This method helps us manage the indices of the stock prices in a manner that enables us to compute the span in O(N) time complexity. Given that we are preparing for an interview, achieving minimal time complexity in calculating the stock price span is crucial.

Step-by-Step Stock Span Solution

1. Initialize a stack and a span array.
2. Iterate through the stock prices.
3. For each price, pop elements from the stack while the stack is not empty and the top element of the stack is less than or equal to the current price.
4. The span of the current price is the difference between the current index and the index of the last element remaining in the stack (or the current index + 1 if the stack is empty).
5. Push the current index onto the stack.

Now that we understand the logic behind the stock price span with real-world example, let’s implement the stock span algorithm in Python in the next section.

Implementing the Stock Span Solution in Python

I have divided the stock span algorithm into small steps so understanding each part will help in remembering during interviews. We have the following steps: ‘Initialize Variables’, ‘Calculate Span Using a Stack’, and finally ‘Finalizing the Solution’.

Step 1: Initialize Variables

First, create the required variables: a list to store the span for each day and a stack to help with the calculations.

def calculateSpan(prices, n):
    span = [0] * n  # Array to store the span values
    stack = []      # Stack to store indices

Step 2: Calculate Span Using a Stack

Iterate through each price, calculate the span using the stack, and update the span array.

def calculateSpan(prices, n):
    span = [0] * n
    stack = []

    for i in range(n):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()

        if not stack:
            span[i] = i + 1
        else:
            span[i] = i - stack[-1]

        stack.append(i)

    return span

Step 3: Finalizing the Solution

Test the function with example inputs to ensure it works as expected.

# Example usage:
prices = [100, 80, 60, 70, 60, 75, 85]
n = len(prices)
print(calculateSpan(prices, n))  # Output: [1, 1, 1, 2, 1, 4, 6]

Summarizing the Stock Span Problem Solution

The Stock Span Problem involves calculating the span of stock prices for each day in an efficient manner. Using a stack to keep track of indices allows us to solve the problem in O(N) time complexity, which is optimal for handling large input sizes.

By following these steps, you can effectively solve the Stock Span Problem in Python and be well-prepared for related interview questions.

FAQs