Stock Span Problem Using Stack in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stock Span Calculation

What is the output of the following code that calculates the stock span for given prices?

DSA Python

def calculate_span(prices):
    stack = []
    span = [0] * len(prices)
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] <= price:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return span

prices = [100, 80, 60, 70, 60, 75, 85]
print(calculate_span(prices))

A [1, 1, 1, 2, 1, 4, 6]

B [1, 2, 3, 1, 2, 1, 1]

C [1, 1, 2, 2, 3, 4, 5]

D [1, 1, 1, 1, 1, 1, 1]

💡 Hint

Remember the span counts how many consecutive days before the current day had prices less than or equal to today's price.

The code uses a stack to keep track of indices of days with higher prices. For each day, it pops days with prices less or equal to current price, then calculates span as distance from last higher price day or start.

🧠 Conceptual

intermediate

Understanding Stack Usage in Stock Span

Why do we use a stack to solve the Stock Span Problem efficiently?

A To store all prices in sorted order for binary search.

B To reverse the prices array for backward traversal.

C To keep track of indices of days with prices greater than the current day's price for quick span calculation.

D To hold the span values temporarily before final calculation.

💡 Hint

Think about how the stack helps avoid checking all previous days repeatedly.

The stack stores indices of days with prices greater than the current day's price, allowing us to quickly find the nearest higher price day to calculate the span without scanning all previous days.

🔧 Debug

advanced

Identify the Error in Stock Span Code

What error does the following code produce when run?

DSA Python

def calculate_span(prices):
    stack = []
    span = [0] * len(prices)
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] < price:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return span

prices = [100, 80, 60, 70, 60, 75, 85]
print(calculate_span(prices))

A The code produces incorrect span values due to missing equality in comparison.

B The output is [1, 1, 1, 3, 1, 4, 6]

C The output is [1, 1, 1, 1, 1, 1, 1]

D The output is [1, 1, 1, 2, 1, 4, 6]

💡 Hint

Check the condition inside the while loop carefully.

The code uses '<' instead of '<=' in the while loop condition, so it does not pop indices with prices equal to current price, causing incorrect span calculation.

❓ Predict Output

advanced

Output of Stock Span with All Increasing Prices

What is the output of the stock span calculation for strictly increasing prices?

DSA Python

def calculate_span(prices):
    stack = []
    span = [0] * len(prices)
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] <= price:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return span

prices = [10, 20, 30, 40, 50]
print(calculate_span(prices))

A [1, 1, 1, 1, 1]

B [1, 2, 3, 4, 5]

C [5, 4, 3, 2, 1]

D [1, 2, 1, 2, 1]

💡 Hint

In strictly increasing prices, each day's price is higher than all previous days.

Since each price is higher than all previous prices, the span for each day is the count of all previous days plus the current day, resulting in increasing span values.

🧠 Conceptual

expert

Time Complexity of Stock Span Algorithm

What is the time complexity of the stock span algorithm using a stack for n prices, and why?

A O(n log n) because of sorting the prices before processing.

B O(n^2) because for each price, we may check all previous prices.

C O(log n) because the stack maintains sorted order for binary search.

D O(n) because each element is pushed and popped at most once from the stack.

💡 Hint

Consider how many times each price index is pushed and popped from the stack.

Each price index is pushed once and popped at most once, so the total operations are proportional to n, making the algorithm O(n).

Practice

1. What does the Stock Span Problem calculate for each day in a list of stock prices?

easy

A. The maximum stock price in the entire list

B. The number of consecutive days before the current day with price less than or equal to current day's price

C. The difference between current day's price and previous day's price

D. The total sum of stock prices up to the current day

Solution

1. Step 1: Understand the problem goal

   The Stock Span Problem finds how many days before today had prices less than or equal to today's price consecutively.

2. Step 2: Clarify what is counted

   It counts consecutive days backward until a higher price is found or start is reached.

3. Final Answer:

   The number of consecutive days before the current day with price less than or equal to current day's price -> Option B

4. Quick Check:

   Span counts consecutive lower/equal prices [OK]

Hint: Span counts consecutive days with price ≤ today's price [OK]

Common Mistakes:

• Thinking it counts all previous days regardless of price
• Confusing span with price difference
• Assuming it finds max price instead

2. Which of the following Python code snippets correctly initializes an empty stack for solving the Stock Span Problem?

easy

A. stack = None

B. stack = {}

C. stack = []

D. stack = ()

Solution

1. Step 1: Identify correct stack data structure

   In Python, a stack is commonly implemented using a list, so an empty stack is an empty list: stack = []

2. Step 2: Check other options

   {} is a dictionary, () is a tuple (immutable), None is no value, so they are incorrect for stack.

3. Final Answer:

   stack = [] -> Option C

4. Quick Check:

   Empty list is stack [OK]

Hint: Use empty list [] to start a stack in Python [OK]

Common Mistakes:

• Using {} which is a dictionary, not stack
• Using () which is immutable tuple
• Assigning None instead of a list

3. What is the output of the following code snippet for prices = [100, 80, 60, 70, 60, 75, 85]?

def calculate_span(prices):
    stack = []
    span = [0]*len(prices)
    for i in range(len(prices)):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return span

print(calculate_span(prices))

medium

A. [1, 1, 1, 2, 1, 4, 6]

B. [1, 2, 3, 4, 5, 6, 7]

C. [7, 6, 5, 4, 3, 2, 1]

D. [1, 1, 2, 2, 3, 3, 4]

Solution

1. Step 1: Trace the loop and stack operations

   For each price, pop indices with prices ≤ current price, then calculate span as distance from last higher price index or i+1 if none.

2. Step 2: Calculate spans for each day

   Day 0: stack empty, span=1; Day 1: price 80 ≤ 100? No pop, span=1; Day 2: 60 ≤ 80? No pop, span=1; Day 3: 70 > 60 pop index 2, span=2; Day 4: 60 ≤ 70 no pop, span=1; Day 5: 75 > 60 pop index 4, 75 > 70 pop index 3, span=4; Day 6: 85 > 75 pop index 5, 85 > 100 no pop, span=6.

3. Final Answer:

   [1, 1, 1, 2, 1, 4, 6] -> Option A

4. Quick Check:

   Span array matches expected output [OK]

Hint: Pop smaller prices, span = current index - last higher index [OK]

Common Mistakes:

• Not popping all smaller or equal prices
• Calculating span as i instead of difference
• Confusing span with price values

4. Identify the error in this Stock Span code snippet:

def stock_span(prices):
    stack = []
    span = []
    for i in range(len(prices)):
        while stack and prices[stack[-1]] < prices[i]:
            stack.pop()
        if not stack:
            span.append(i)
        else:
            span.append(i - stack[-1])
        stack.append(i)
    return span

print(stock_span([10, 4, 5, 90, 120, 80]))

medium

A. Stack is not initialized correctly

B. The function returns None instead of span list

C. Comparison operator should be <= instead of <

D. Span for first day should be 1, but code appends 0

Solution

1. Step 1: Check span calculation for first day

   When stack is empty, span should be i+1 (1 for first day), but code appends i (0 for first day), causing wrong span.

2. Step 2: Confirm other parts are correct

   Stack initialization and popping logic are fine; comparison operator < is acceptable; function returns span list correctly.

3. Final Answer:

   Span for first day should be 1, but code appends 0 -> Option D

4. Quick Check:

   Span for day 0 must be 1 [OK]

Hint: Span on empty stack = i+1, not i [OK]

Common Mistakes:

• Appending i instead of i+1 when stack empty
• Using wrong comparison operator causing wrong pops
• Not initializing span list properly

5. Given a list of stock prices, how would you modify the Stock Span algorithm to handle the case where prices can be equal and you want the span to include days with strictly less price only (exclude equal prices)?

hard

A. Change the comparison in while loop to prices[stack[-1]] < prices[i]

B. Change the comparison in while loop to prices[stack[-1]] <= prices[i]

C. Add an extra condition to skip equal prices after popping

D. No change needed; current algorithm already excludes equal prices

Solution

1. Step 1: Understand current comparison

   Current algorithm uses <= to pop indices with prices less than or equal to current price, including equal prices in span.

2. Step 2: Modify to exclude equal prices

   To exclude equal prices, change comparison to strictly less than (<) so equal prices stop popping and are not included in span.

3. Final Answer:

   Change the comparison in while loop to prices[stack[-1]] < prices[i] -> Option A

4. Quick Check:

   Use < to exclude equal prices [OK]

Hint: Use < instead of <= to exclude equal prices in span [OK]

Common Mistakes:

• Using <= keeps equal prices included
• Adding extra conditions unnecessarily
• Assuming no change is needed