Explain the stock span problem and its solution.
A classic problem where you calculate the span of stock prices, defined as the number of consecutive days the price was less than or equal to the current price.
Why Interviewers Ask This
This problem tests your ability to use monotonic stacks to solve range queries efficiently. It is a common pattern in financial algorithms and time-series analysis.
How to Answer This Question
Define the span clearly. Explain the brute force O(N^2) approach first. Then introduce the monotonic stack approach where you store indices of decreasing prices. For each new price, pop elements smaller than the current price to find the nearest greater element. Calculate span as the difference between current index and the index of the greater element. Highlight O(N) time complexity.
Key Points to Cover
- Use a Monotonic Stack for efficiency
- Pop elements smaller than current price
- Calculate span based on index difference
- Achieve O(N) time complexity
Sample Answer
The stock span problem asks us to find how many consecutive days the price was less than or equal to today's price. A brute force solution checks all previous days, which is slow. Instead, I use a monotonic stack to stor…
Common Mistakes to Avoid
- Using a simple loop for every element
- Forgetting to push the current index
- Misinterpreting the definition of span
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.