How to Solve Stock Span Problem on LeetCode
The Stock Span Problem is a classic application of the monotonic stack, often asked to test your ability to reason about "previous greater" relationships in arrays.
Problem Statement
Given a list of daily stock prices, return the span of stock’s price for all days. The span is the number of consecutive days before today where the price was less than or equal to today’s price.
Example:
Input: prices = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Why This Problem Matters for Interviews
This problem:
- Reinforces monotonic stack techniques
- Highlights your understanding of array-index relationships
- Prepares you for similar "next/previous greater" problems
Stack-Based Approach (Optimal)
Track indices of prices with a stack, pop until the stack top is greater than current price.
Time Complexity: O(n)
Space Complexity: O(n)
def calculateSpan(prices: list[int]) -> list[int]:
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
Key Interview Talking Points
- Why a stack is better than nested loops for span calculation
- The role of indices vs values in the stack
- Monotonic property and span updates
- Handling the first day/element
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack | O(n) | O(n) |
Pro Interview Tips
- Step through the stack on sample input.
- Explain when and why stack elements are popped.
- Practice with test cases