What is the stock span problem and how do you solve it efficiently?
Direct Answer
This question involves calculating the span of stock prices over consecutive days. It tests monotonic stack applications and pattern recognition.
Why Interviewers Ask This
The stock span problem is a classic example of applying stacks to find the nearest greater element to the left. It demonstrates the candidate's ability to optimize a naive O(N^2) solution to O(N).
How to Answer This Question
Define the span as the number of consecutive days before the current day where the price was lower. Use a monotonic decreasing stack to store indices of prices. For each new price, pop elements smaller than the current price and calculate the span based on the index of the remaining top element.
Key Points to Cover
- Define span correctly
- Use monotonic decreasing stack
- Pop smaller elements
- Calculate span using indices
Sample Answer
The span is the count of consecutive days prior to today where the price was less than or equal to today's price. I can solve this using a stack to store indices. For each day, I pop indices from the stack where the pric…
Common Mistakes to Avoid
- Using a brute force nested loop
- Forgetting to push current index
- Handling equal prices incorrectly
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.