Algotree > Algorithms > Stack > Stock Span Problem

Stock Span Problem

Stock Span problem is based on some financial data like the prices of a stock for a given number of days. Thus, we have

Available data : A list of stock prices for N consecutive number of days.
Objective : Finding the stock span i.e finding the number of consecutive days before a specific day D when the price of a given stock was less than or equal to the price of a stock on day D.

Example : In the below bar chart,

The stock span for D₀ is 1 as there are no stock prices listed before day D₀.
The stock span for D₃ is 3 as there are 2 stock prices that are less than or equal to the stock price on day D₃ i.e [ D₂ and D₁ ].

stock_span

C++ : Finding the stock span using brute force.

Note : Brute force approach for finding the stock span in not efficient as it sequentially checks the stock prices of all the previous days for a given day.

Time complexity of brute force approach : O ( N² ), where N is the number of days with the listed stock prices.

#include<iostream>
#include<vector>

using namespace std;
vector<int> FindStockSpan (const vector<int>& stock_price) { 

    int N = stock_price.size();  

    //Span for each day would always be atleast 1  
    vector<int> span (N, 1); 

    for (int today = 1; today < N; today++) {

        for (int  previous = today - 1; previous >= 0; previous--) {
            if (stock_price[today] >= stock_price[previous]) {
                span[today]++;
            } else {
                // Stock price of the previous day greater than today, 
                // so stop checking the price of the previous days.
                break;
            }   
        }   
    }   
    return span;
}
 
int main() {

    const vector<int> prices = { 10, 4, 2, 4, 6, 8, 6, 8 };  
  
    vector<int> span = FindStockSpan(prices);

    cout << "Stock span for the prices ..." << endl;
    for (const auto& s : span) {
         cout << s << " ";
    }   
    return 0;  
}

Output

Stock span for the prices ...
1 1 1 3 4 5 1 7

Algorithm : Finding the Stock Span Using Stack

Stack is used to store the index of the stock prices i.e the day numbers.
List stores the stock span for each day.
Initialize the stock span for day 0 as 1. i.e span [ 0 ] = 1
Push the index of the first day i.e 0 into the stack. Stack [ 0 ] = 0
For day D from 1 upto N-1 do the following
While (Stack is not Empty) and price [ D ] >= price [ stack.top ( ) ] do
stack.pop ( )
If the stack is not Empty then
span [ D ] = D - stack.top ( )
Else
span [ D ] = D + 1
Push current day D on top of stack. i.e stack.push ( D )

Example
Stock Prices: [ 10, 4, 2, 4, 6, 8, 6, 8 ]

Steps	Day D	Price on day D	Operation	Span	Stack Content
1.	0	10	Initialize	Base Case : Span for day 0 would always be 1. i.e Span [ 0 ] = 1	Base Case : Stack [ 0 ] = 0
2.	1	4	price [ day 1 ] < price [ 0 (stack top) ] i.e 4 < 10 Cannot pop the index of the stock price. Calculate the span.	Span [ 1 ] = 1 - 0 = 1	Push day 1 on stack top. Stack [ 1 ] = 1 Stack [ 0 ] = 0
3.	2	2	price [ day 2 ] < price [ 1 (stack top) ] i.e 2 < 4 Cannot pop the index of the stock price. Calculate the span.	Span [ 2 ] = 2 - 1 = 1	Push day 2 on stack top. Stack [ 2 ] = 2 Stack [ 1 ] = 1 Stack [ 0 ] = 0
4.	3	4	price [ day 3 ] > price [ 2 (stack top) ] i.e 4 > 2 Pop day 2 from the stack. price [ day 3 ] > price [ 1 (stack top) ] i.e 4 >= 4 Pop day 1 from the stack. price [ day 3 ] < price [ 0 (stack top) ] i.e 4 < 10 Cannot pop the index of the stock price. Calculate the span.	Span [ 3 ] = 3 - 0 = 3	Push day 3 on stack top Stack [ 1 ] = 3 Stack [ 0 ] = 0
5.	4	6	price [ day 4 ] > price [ 3 (stack top) ] i.e 6 > 4 Pop day 3 from the stack. price [ day 4 ] < price [ 0 (stack top) ] i.e 6 < 10 Cannot pop the index of the stock price. Calculate the span.	Span [ 4 ] = 4 - 0 = 4	Push day 4 on stack top Stack [ 1 ] = 4 Stack [ 0 ] = 0
6.	5	8	price [ day 5 ] > price [ 4 (stack top) ] i.e 8 > 6 Pop day 4 from the stack. price [ day 5 ] < price [ 0 (stack top) ] i.e 8 < 10 Cannot pop the index of the stock price. Calculate the span.	Span [ 5 ] = 5 - 0 = 5	Push day 5 on stack top Stack [ 1 ] = 5 Stack [ 0 ] = 0
7.	6	6	price [ day 6 ] < price [ 5 (stack top) ] i.e 6 < 8 Cannot pop the index of the stock price. Calculate the span.	Span [ 6 ] = 6 - 5 = 1	Push day 6 on stack top Stack [ 2 ] = 6 Stack [ 1 ] = 5 Stack [ 0 ] = 0
8.	7	8	price [ day 7 ] > price [ 6 (stack top) ] i.e 8 > 6 Pop day 6 from the stack. price [ day 7 ] > price [ 1 (stack top) ] i.e 8 >= 8 Pop day 5 from the stack. price [ day 7 ] < price [ 0 (stack top) ] i.e 8 < 10 Cannot pop the index of the stock price. Calculate the span.	Span [ 7 ] = 7 - 0 = 7	Push day 7 on stack top Stack [ 1 ] = 7 Stack [ 0 ] = 0

Calculated Span: [ 1, 1, 1, 3, 4, 5, 1, 7 ]

Time complexity : O ( N ), where N is the number of days with the listed prices.

Implementation of the Stock Span problem

def FindStockSpan (prices):
    
    stack_days = [] # Stack to hold the days
    span = []

    # Base case
    span.append(1) # Span of 1'st day is always 1.
    stack_days.append(0) # Day 0 goes in the stack first.

    for today in range(1, len(prices)):

        # Pop out days from the stack until the price on stack top is greater than
        # or equal to the price on the current day. 
        while len(stack_days) > 0 and prices[today] >= prices[stack_days[-1]]:
            stack_days.pop()

        # Set the stockspan values.
        if len(stack_days) > 0:
            span.append(today - stack_days[-1])
        else:
            span.append(today + 1)  

        stack_days.append(today)

    print("Stock Prices ...")
    print(prices)
    print("Stock Stock Span...")
    print(span)
    print("\n")
        
def main():
    prices = [10, 4, 2, 4, 6, 8, 6, 8]
    FindStockSpan(prices)
    prices.clear()

    prices = [9, 10, 10, 8]
    FindStockSpan(prices)
    prices.clear()
        
    prices = [40, 40] 
    stockspan = FindStockSpan(prices)

if __name__ == "__main__":
    main()

Output

Stock Prices ...
[10, 4, 2, 4, 6, 8, 6, 8]
Stock Stock Span...
[1, 1, 1, 3, 4, 5, 1, 7]


Stock Prices ...
[9, 10, 10, 8]
Stock Stock Span...
[1, 2, 3, 1]


Stock Prices ...
[40, 40]
Stock Stock Span...
[1, 2]

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

vector<int> FindStockSpan (const vector<int>& price) {

    int N = price.size();

    vector<int> span(N);
    stack<int> stk_days;

    // Base cases
    span[0] = 1;      // Span of day 0 would always be 1
    stk_days.push(0); // Push day 0 into the stack.

    for (int today = 1; today < N; today++) {

        // While the price of the stack today is greater than price stored at the
        // top of the stack.
        while (!stk_days.empty() && price[today] >= price[stk_days.top()]) {
            stk_days.pop();
        }

        // Calculate the span.
        if(!stk_days.empty()) {
           span[today] = today - stk_days.top();
        } else {
           span[today] = today + 1;
        }

        // Push current day into the stack.
        stk_days.push(today);
    }   
    return span;
}

void DisplaySpan(const vector<int> & prices, const vector<int>& span) {

    cout << "\n\nStock Prices ..." << endl;
    for (const auto& s : prices) {
         cout << s << " " ;
    }   

    cout << "\n\nStock span for the prices ..." << endl;
    int day = 0;
    for (const auto& s : span) {
         cout << "Day " << day++ << " : " << s << " " << endl;
    }   
} 

int main() {

    const vector<int> stock_prices_a = { 10, 4, 2, 4, 6, 8, 6, 8 };
    vector<int> span_a = FindStockSpan(stock_prices_a);
    DisplaySpan(stock_prices_a, span_a);

    const vector<int> stock_prices_b = { 9, 10, 10, 8 };
    vector<int> span_b = FindStockSpan(stock_prices_b);
    DisplaySpan(stock_prices_b, span_b);

    const vector<int> stock_prices_c = { 4, 4 };
    vector<int> span_c = FindStockSpan(stock_prices_c);
    DisplaySpan(stock_prices_c, span_c);
    
    return 0;
}

Output

Stock Prices ...
10 4 2 4 6 8 6 8 

Stock span for the prices ...
Day 0 : 1 
Day 1 : 1 
Day 2 : 1 
Day 3 : 3 
Day 4 : 4 
Day 5 : 5 
Day 6 : 1 
Day 7 : 7 


Stock Prices ...
9 10 10 8 

Stock span for the prices ...
Day 0 : 1 
Day 1 : 2 
Day 2 : 3 
Day 3 : 1 


Stock Prices ...
4 4 

Stock span for the prices ...
Day 0 : 1 
Day 1 : 2