Stock Span Problem

What is the 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,

  1. The stock span for D0 is 1 as there are no stock prices listed before day D0.
  2. The stock span for D3 is 3 as there are 2 stock prices that are less than or equal to the stock price on day D3 i.e [ D2 and D1 ].

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 ( N2 ), 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

  1. Stack is used to store the index of the stock prices i.e the day numbers.
    List stores the stock span for each day.
  2. 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
  3. For day D from 1 upto N-1 do the following
  4.       While (Stack is not Empty) and price [ D ] >= price [ stack.top ( ) ] do
                stack.pop ( )
  5.       If the stack is not Empty then
                span [ D ] = D - stack.top ( )
  6.       Else
                span [ D ] = D + 1
  7.       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 
import java.util.List;
import java.util.Stack;
import java.util.Arrays;
import java.util.ArrayList;

class StockSpan {

    // Function to calculate the stock span
    public List<Integer> FindStockSpan (List<Integer> price) {

        int N = price.size();

        List<Integer> span = new ArrayList<Integer>();
        Stack<Integer> stk_days = new Stack<Integer>();

        // Base cases
        span.add(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.get(today) >= price.get(stk_days.peek())) {
                stk_days.pop();
            }

            // Calculate the span.
            if(!stk_days.empty()) {
               span.add(today, today - stk_days.peek());
            } else {
               span.add(today, today + 1);
            }

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

    public void DisplaySpan (List<Integer> prices, List<Integer> span) {

        System.out.println("\n\nStock Prices ...");
        for (Integer s : prices) {
             System.out.print(s + " ");
        }

        System.out.println("\n\nStock span for the prices ...");
        int day = 0;
        for (Integer s : span) {
             System.out.println("Day " + day + " : " + s);
             day++;
        }
    }

    public static void main (String[] args) {

        StockSpan sp = new StockSpan();

        List<Integer> stock_prices_a = Arrays.asList(10, 4, 2, 4, 6, 8, 6, 8);
        List<Integer> span_a = sp.FindStockSpan(stock_prices_a);
        sp.DisplaySpan(stock_prices_a, span_a);

        List<Integer> stock_prices_b = Arrays.asList(9, 10, 10, 8);
        List<Integer> span_b = sp.FindStockSpan(stock_prices_b);
        sp.DisplaySpan(stock_prices_b, span_b);

        List<Integer> stock_prices_c = Arrays.asList(5, 5);
        List<Integer> span_c = sp.FindStockSpan(stock_prices_c);
        sp.DisplaySpan(stock_prices_c, span_c);
    }
}

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 ...
5 5 

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



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.