Solve Stock Span Problem in C++
By Prayas SambhareHello! In this post, we will study the stock span problem with the help of the C++ program. Let us understand the problem first.
You are given a list of ‘n’ daily prices for a stock. You are asked to calculate the total number of consecutive days (before a particular day) once the value of the stock was less than or equal to the value on this particular day called stock span.
The Stock Span, S(i) on a given day ‘i’ = the maximum number of consecutive days before the day ‘i’ such that the stock price is less than or equal to the price on the day ‘i’.
You have the prices for 1 week in the form of an array or list: {90, 80, 40, 70, 30, 60, 55}. You have to find out the span values for each day. In this example, the span values are {1,1,1,2,1,2,1} (You just have to find the maximum number of consecutive days before the given day such that the stock price is less than or equal to the price on the given day).
Solving The Stock Span Problem using C++ stack
Although you can solve the Stock Span problem by using a brute force algorithm, it will be inefficient and the time complexity will be O(n²). Instead, we can improve the time complexity to O(n) by using the following approach:
- Put the stock-prices in an array and create another array stock-span with size = size of the stock-prices array’s size.
- You have to create a stack and initialize the first element of the stock-span array to 1 i.e. stock-span[0] = 1.
- You have to iterate through the stock-prices array with a for loop for all the days (days=size of the stock-prices array).
- After calculating the stock-span for a day. you have to add it to the stock-span array and push the index of this element into the stack.
- You have to check the stock-price that corresponds to the index on top of the stack.
- Then pop the elements until the stack becomes empty or the price at the top of the stack is larger than the one we are pushing.
C++ Program to Solve The Stock Span Problem
#include <bits/stdc++.h>
using namespace std;
void stock_span_calculator(int stock_prices[], int days, int stock_span[]){
stack<int> stack;
stock_span[0] = 1;
stack.push(0);
for(int i=1; i<days; i++)
{
while(stock_prices[i] > stock_prices[stack.top()])
{
stack.pop();
if(stack.empty())
{
break;
}
}
if(stack.empty())
{
stock_span[i] = i+1;
}
else
{
stock_span[i] = i - stack.top();
}
stack.push(i);
}
}
int main() {
int days = 7;
int stock_prices[days] = {90, 80, 40, 70, 30, 60, 55};
int stock_span[days];
stock_span_calculator(stock_prices, days, stock_span);
cout << "The stock-span values are:" << endl;
for(int i=0; i<days; i++)
{
if(i!=0){
cout << ", ";
}
cout<< stock_span[i];
}
cout << endl;
}
Output for the above Code
The stock-span values are: 1, 1, 1, 2, 1, 2, 1
The stock span problem is a financial problem. There is an array of integers that contains the prices of stocks for n consecutive days. Our task is to find the span of stock for each day.
Now, what is the span?
Span on a day is the number of consecutive days just before the current day and including the current day, for which the price of the stock is equal or smaller than the price of the stock for the current day.
Let’s see another example:
Understanding the stock span problem
Let us take an example:
Array of prices of stock = {40, 35, 37, 36, 41}
Span of stock for each day = {1, 1, 2, 1, 5}At day 1, the span is 1 because there are no days before day-1 for which the price is equal or smaller.
For the day-2, the span is again 1 as the price on day-1 is 40 which is greater than 35.
At day 3, the span is 2 because the day-2 price is 35 which is less than 37.
For day-4, span is 1 as 36 is less than 37.
At day-5 span is 5 because there are 5 days (including day-5) for which the price is smaller than the price at day 5 (which is 41).
Let us see the code implementation.
Here I will be discussing two methods to solve the stock span problem. The first one is the naive method and other one is the efficient method.
Naive Method
This method takes O(n^2) time and constant space. See the given C++ code below:
#include <bits/stdc++.h>
using namespace std;
vector<int> fill_span(int price[],int n){
vector<int>span_arr(n);
span_arr[0] = 1;
int span = 1;
for(int i=1;i<n;i++){
span = 1;
for(int j=i-1;j>=0;j--){
if(price[j]<=price[i]){
span++;
}
else
break;
}
span_arr[i] = span;
}
return span_arr;
}
int main()
{
int price[] = { 10, 4, 5, 90, 120, 80 };
int n = sizeof(price) / sizeof(price[0]);
vector<int>span = fill_span(price, n);
for(int i=0;i<n;i++){
cout << span[i] <<" ";
}
return 0;
}Output:
1 1 2 4 5 1
Let us understand what is going on here.
For each day we are counting the number of consecutive days before it for which the price of the stock is equal or smaller than the price of the stock for the current day. It is a pretty straight forward code and very easy to understand and it takes O(n^2) time for the worst case. The worst-case for the problem is when the price array is sorted in an ascending manner.
Efficient Method
The efficient method takes O(n) time and O(n) space.
#include <bits/stdc++.h>
using namespace std;
vector<int> fill_span(int price[], int n)
{
vector<int>v(n);
stack<int>s;
s.push(0);
v[0]=1;
for(int i=1;i<n;i++){
while(s.empty()!=true && price[i]>=price[s.top()]){
s.pop();
}
if(s.empty()==true){
v[i] = i+1;
}
else{
v[i] = i-s.top();
}
s.push(i);
}
return v;
}
int main()
{
int price[] = { 10, 4, 5, 90, 120, 80 };
int n = sizeof(price) / sizeof(price[0]);
vector<int>span = fill_span(price, n);
for(int i=0;i<n;i++){
cout << span[i] <<" ";
}
return 0;
}Output:
1 1 2 4 5 1
Let us understand the efficient method.
First, note that the span[i] = i – index of the immediate day when the price greater than price[i].
For example : For the price array = {10, 4, 5, 90, 120, 80}, the span at day-3 will be calculated as index of 5 – index of 10 which is equal to 2-0=2.
For any day i if the price at day i-1 is greater than the price of day i then span[i] = 1. And if the price at day i-1 is smaller than the price of the day i then we search for the day before the day i-1 for which the price is greater than the day i and put span[i] = i – index of the day we found. If there is no such day found then span[i] will be i+1.
For the purpose of searching and storing the immediate day when the price greater than price[i] we use of stack data structure where we store the index of the days.
Dry Run for the code
For input price array = {10, 4, 5, 90, 120, 80}
span[0] = 1;
stack = 0]
for i=1 => We compare price[i] with top element of stack (which is 10) and see that 4 < 10 so we put span[1] = i – s.top() = 1-0 = 0. Push 1 to stack. Thus stack becomes 1, 0].
i=2 => Compare 5 with 4 and 5 > 4 therefore remove 4 from stack. Again compare 5 with 10 and 5<10 thus span[2] = i-s.top() = 2-0 = 2. Push 2 to stack. Thus stack becomes 2, 0]
i=3 => Compare 90 and 5. Here 90 > 5 so we remove 5 from stack. Again compare 90 with 10 and 10<90 so we remove 10. And now the stack becomes empty. This essentially means that there is no number greater than 90 on the left of 90 hence span[3] = i+1 = 3+1 = 4. Push 3 to stack. Thus stack becomes 3]
i=4 => Compare 120 with with 90. Here 120>90 so we remove 90 from stack. The stack becomes empty and thus span[4] = 4 + 1 = 5. Push 4 to the stack. Thus stack becomes 4].
i=5=> Compare 80 with with 120. Here 80<120 so we put span[5] = 5 – 4 = 1.
Thus the span array is created.
Note:- The efficient method takes O(n) space in the worst case when the price array is sorted in a descending manner.
Hope you got to understand the stock span problem in C++. Thank You!
Check out my other blog posts:-
Knuth-Morris-Pratt (KMP) Algorithm in C++
Rabin Karp algorithm for pattern matching in C++
Leave a Reply