Master the Stock Span Problem by 3 Easy Steps in Python

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

Go ahead and check them out before going to your interview!

Master the Stock Span Problem by 3 Easy Steps in Python
Find the largest sum subarray using Kadanes Algorithm
Mastering Object-Oriented Programming in C++
Palindrome Partitioning A Comprehensive Guide
what is parameter in coding and what is the deference between param and argument in programming
how to inverse a matrix in c#

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 share prices. The span of a share’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 share on the current day is less than or equal to its price on the given day.

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

Implementing the Stock Span Solution in Python

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.