The stock span problem is a financial problem where we have a series of daily price quotes for a stock and we need to calculate the span of the stock's price for each day. The span of the stock's price for a particular day is defined as the maximum number of consecutive days (including the current day) for which the stock price is less than or equal to the price of the current day.
Example:
Input: [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Explanation:
- For day 1 (100), the span is 1, as it is the first day.
- For day 2 (80), the span is 1, as the previous day's price (100) is greater.
- For day 3 (60), the span is 1, as the previous day's price (80) is greater.
- For day 4 (70), the span is 2, as the previous day's price (60) is smaller, so we include the day before that (60).
- For day 5 (60), the span is 1, as the previous day's price (70) is greater.
- For day 6 (75), the span is 4, as the previous day's price (60) is smaller, so we include the three days before that (60, 70, 60).
- For day 7 (85), the span is 6, as the previous day's price (75) is smaller, so we include the five days before that (60, 70, 60, 75, 85).
There are many ways to solve this problem, popularly it is solved using stack or dynamic programming and here we are going to discuss all these approaches in detail starting with the brute force approach.
Stock Span Problem Using Brute Force Approach.
In this approach, for each day, we traverse backward and count the number of consecutive days with prices less than or equal to the current day's price. Traverse backward from i-1 to 0 and for each previous day j, compare the stock price at day i with the stock price at day j.
Below is the code implementation of the above approach:
// Cpp program for stock span problem (brute force) #include <iostream> #include <vector> using namespace std; vector<int> calculateSpan(const vector<int>& prices) { int n = prices.size(); vector<int> span(n, 1); for (int i = 0; i < n; ++i) { int spanValue = 1; //traverse backwards and count the number of consecutive days for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) { spanValue++; } span[i] = spanValue; } return span; } int main() { vector<int> stockPrices = {100, 80, 60, 70, 60, 75, 85}; vector<int> span = calculateSpan(stockPrices); cout << "Stock Prices: "; for (int price : stockPrices) { cout << price << " "; } std::cout << "\nSpans: "; for (int s : span) { std::cout << s << " "; } return 0; }
// Java program for stock span problem - brute force approach import java.util.Arrays; public class StockSpan { public static void main(String[] args) { int[] prices = {100, 80, 60, 70, 60, 75, 85}; int[] span = calculateSpan(prices); System.out.println("Stock Prices: " + Arrays.toString(prices)); System.out.println("Spans: " + Arrays.toString(span)); } public static int[] calculateSpan(int[] prices) { int n = prices.length; int[] span = new int[n]; Arrays.fill(span, 1); for (int i = 0; i < n; ++i) { int spanValue = 1; //traverse backwards and count the number of consecutive days for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) { spanValue++; } span[i] = spanValue; } return span; } }
# Python program to solve stock span problem def calculate_span(prices): n = len(prices) span = [1] * n for i in range(1, n): span_value = 1 for j in range(i - 1, -1, -1): if prices[j] > prices[i]: break span_value += 1 span[i] = span_value return span stock_prices = [100, 80, 60, 70, 60, 75, 85] span = calculate_span(stock_prices) print("Stock Prices: " + str(stock_prices)) print("Spans: " + str(span))
// C# code to solve stock span problem - brute force using System; class StockSpan { public static void Main() { int[] prices = {100, 80, 60, 70, 60, 75, 85}; int[] span = CalculateSpan(prices); Console.WriteLine("Stock Prices: " + string.Join(" ", prices)); Console.WriteLine("Spans: " + string.Join(" ", span)); } public static int[] CalculateSpan(int[] prices) { int n = prices.Length; int[] span = new int[n]; Array.Fill(span, 1); for (int i = 0; i < n; ++i) { int spanValue = 1; for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) { spanValue++; } span[i] = spanValue; } return span; } }
Stock Prices: 100 80 60 70 60 75 85
Spans: 1 1 1 2 1 4 6
Time Complexity: O(n^2).
Space Complexity: O(1).
Stock Span Problem Using Stack.
In this approach, we utilize a stack to efficiently calculate the span of stock prices. We traverse the array of stock prices once and maintain a stack of previous days' indices along with their corresponding span values. Below are the algorithm steps that you follow for better understanding.
Algorithm Steps:
- Create an empty stack to store indices.
- Initialize an array span of the same size as the number of days, initially filled with zeros. This array will store the span for each day.
- Iterate through each day, starting from the first day.
- -- While the stack is not empty and the price of the stock on the current day is greater than the price on the day represented by the index at the top of the stack: Pop the index from the stack.
- -- If the stack is empty, set the span for the current day as the current day itself; otherwise, set it as the difference between the current day and the day represented by the index at the top of the stack.
- -- Push the current day's index onto the stack.
- After completing the iteration, the span array contains the span for each day.
Below is the code implementation for the above approach:
// Stock span problem using stack #include <iostream> #include <stack> #include <vector> using namespace std; vector<int> calculateSpan(const vector<int>& prices) { stack<int> st; vector<int> span(prices.size(), 0); for (int i = 0; i < prices.size(); ++i) { while (!st.empty() && prices[i] >= prices[st.top()]) { st.pop(); } span[i] = st.empty() ? i + 1 : i - st.top(); st.push(i); } return span; } int main() { vector<int> prices = {100, 80, 60, 70, 60, 75, 85}; vector<int> span = calculateSpan(prices); cout << "Stock Prices: "; for (int price : prices) { cout << price << " "; } cout << "\nStock Spans: "; for (int s : span) { cout << s << " "; } return 0; }
// Stock Span Problem Using Stack import java.util.Stack; import java.util.Arrays; public class StockSpan { public static void main(String[] args) { int[] prices = {100, 80, 60, 70, 60, 75, 85}; int[] span = calculateSpan(prices); System.out.println("Stock Prices: " + Arrays.toString(prices)); System.out.println("Stock Spans: " + Arrays.toString(span)); } public static int[] calculateSpan(int[] prices) { Stack<Integer> st = new Stack<>(); int[] span = new int[prices.length]; for (int i = 0; i < prices.length; i++) { while (!st.isEmpty() && prices[i] >= prices[st.peek()]) { st.pop(); } span[i] = st.isEmpty() ? i + 1 : i - st.peek(); st.push(i); } return span; } }
# Python code for stock span problem using stack def calculate_span(prices): stack = [] span = [0] * len(prices) for i in range(len(prices)): while stack and prices[i] >= prices[stack[-1]]: stack.pop() span[i] = len(stack) if not stack else i - stack[-1] stack.append(i) return span prices = [100, 80, 60, 70, 60, 75, 85] span = calculate_span(prices) print("Stock Prices: " + str(prices)) print("Stock Spans: " + str(span))
// C# code for stock span problem using stack using System; using System.Collections.Generic; public class StockSpan { public static void Main(string[] args) { int[] prices = {100, 80, 60, 70, 60, 75, 85}; int[] span = CalculateSpan(prices); Console.WriteLine("Stock Prices: " + string.Join(" ", prices)); Console.WriteLine("Stock Spans: " + string.Join(" ", span)); } public static int[] CalculateSpan(int[] prices) { Stack<int> st = new Stack<int>(); int[] span = new int[prices.Length]; for (int i = 0; i < prices.Length; i++) { while (st.Count > 0 && prices[i] >= prices[st.Peek()]) { st.Pop(); } span[i] = st.Count == 0 ? i + 1 : i - st.Peek(); st.Push(i); } return span; } }
Output:
Stock Prices: 100 80 60 70 60 75 85
Spans: 1 1 1 2 1 4 6
Time Complexity: O(n).
Space Complexity: O(n).
There are many other approaches as well to solve this problem like by using Dynamic Programming and Monitonic Stack that we have covered separately in other articles.
Trends is an amazing magazine Blogger theme that is easy to customize and change to fit your needs.