How to solve the stock span problem in Python
Calculate the stock span for each day's price using a monotonic stack in O(n) time.
Python code
17 linesdef stock_span(prices):
span = [1] * len(prices)
stack = []
for i in range(len(prices)):
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
span[i] = i - stack[-1] if stack else i + 1
stack.append(i)
return span
if __name__ == "__main__":
prices = [100, 80, 60, 70, 60, 75, 85]
result = stock_span(prices)
print(f"Prices: {prices}")
print(f"Spans: {result}")Output
Prices: [100, 80, 60, 70, 60, 75, 85]
Spans: [1, 1, 1, 2, 1, 4, 6]How it works
The stack stores indices of prices in decreasing order. For each price, we pop indices while the stack's top price is less than or equal to the current price, because those previous days cannot be part of the span. If the stack becomes empty, all previous days are cheaper, so the span is i + 1. Otherwise, the span is the difference between the current index and the index of the last price greater than the current price.
Common mistakes
- Using <= instead of < when comparing prices, which incorrectly drops equal consecutive prices
- Forgetting to handle the empty stack case, leading to IndexError
- Returning the stack or indices instead of the span values
Variations
- Use enumerate(prices) for cleaner indexing in the loop
- Implement recursively with a helper function for a divide-and-conquer approach
Real-world use cases
- Analyzing stock price trends in financial dashboards to identify momentum.
- Computing consecutive days of price increase for algorithmic trading signals.
- Building technical indicators that rely on historical price patterns.
Sponsored
More from Algorithms & data structures
- Binary Search for Ship Capacity in Python medium
- Binary Search on Answer in Python: Koko Eating Bananas medium
- Bucket Numbers into Histogram Bin Counts in Python easy
- Container With Most Water: Two-Pointer Solution in Python medium
- Count Smaller Elements to the Right in Python easy
- Depth First Search Traversal Order in Python easy
Keep learning
Related tutorials and quizzes for this topic.