# 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 ]. 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 = 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
``````