Cracking the Stock Spans Problem: A Stack-Based Solution
The "Stock Spans Problem" is a classic computer science challenge that involves finding the maximum number of consecutive days (including the current day) where the price of a stock has been less than or equal to the current day's price. Imagine you're a stock trader trying to understand the price history of a particular stock. You want to know, for each day, how many days back you need to go before you find a day with a price higher than the current day's price. This information can be valuable for making trading decisions.
Let's break it down with an example. Consider the following stock prices:
Day | Price
-----|-----
1 | 100
2 | 80
3 | 120
4 | 130
5 | 70
6 | 60
7 | 110
The Stock Spans for each day would be:
Day | Price | Span
-----|-----|-----
1 | 100 | 1
2 | 80 | 1
3 | 120 | 3
4 | 130 | 4
5 | 70 | 1
6 | 60 | 1
7 | 110 | 2
The Solution: A Stack to the Rescue
A stack data structure provides an elegant solution to this problem. Here's how it works:
- Initialization: Create an empty stack to store the indices of prices we've encountered.
- Iteration: Iterate through the stock prices from left to right.
- Calculation: For each day:
- While the stack is not empty and the price at the top of the stack is less than or equal to the current price: Pop the top element from the stack. This step ensures that we only consider days with lower or equal prices in our span calculation.
- Calculate the span: If the stack is empty, the span is the current day's index + 1. Otherwise, the span is the difference between the current index and the top element of the stack + 1.
- Push: Push the current index onto the stack.
Code Implementation (Python):
def calculate_stock_spans(prices):
spans = [0] * len(prices)
stack = []
for i in range(len(prices)):
while stack and prices[stack[-1]] <= prices[i]:
stack.pop()
if stack:
spans[i] = i - stack[-1]
else:
spans[i] = i + 1
stack.append(i)
return spans
# Example usage
prices = [100, 80, 120, 130, 70, 60, 110]
stock_spans = calculate_stock_spans(prices)
print(stock_spans) # Output: [1, 1, 3, 4, 1, 1, 2]
Benefits of the Stack Approach:
- Efficiency: The algorithm runs in linear time (O(n)) because each element is pushed and popped at most once onto the stack.
- Clear Logic: The stack effectively keeps track of the previous days with lower or equal prices, allowing for efficient span calculation.
Beyond the Basics:
The stock spans problem can be further extended with variations such as:
- Handling negative prices: The algorithm can be easily adapted to handle negative prices.
- Finding maximum spans: We can modify the algorithm to find the maximum span across all days.
In Conclusion
The stock spans problem is a great illustration of how stacks can be used to solve real-world problems efficiently. By understanding the logic and implementation, you gain valuable insights into utilizing stacks for effective problem-solving. Remember, the key lies in leveraging the stack's LIFO (Last-In, First-Out) nature to track and compare elements, ultimately simplifying the computation.
Resources:
