Stock Span Problem in C++

Hello! In this post, we will study the stock span problem with the help of the C++ program. Let us understand the problem first.

The stock span problem is a financial problem. There is an array of integers that contains 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.

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 price is equal or smaller.
For day-2 span is again 1 as the price at 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

Your email address will not be published. Required fields are marked *