Related Tags

stock span
c++
python

# The stock span problem in C++ and Python

## Stock span

Given a list of rates of a certain stock for some number of days, the stock spanâ€‹ is the number of consecutive days (before a specific day) when the price of the stock was less than or equal to the price on this specific day.

### Implementation

Create a stack and an empty list of stock spans.

Traverse through the list of stock rates:

• For the first day, the stock-span is $1$ by default.
• When youâ€™ve calculated the stock span for a certain day, add this to the corresponding index in the list of stock spans. Push the index of this element onto the stack.
• To calculate the stock span for a certain day:
• Check the stock price that corresponds to the index on top of the stack.
• Compare it with the stock price at the current day. If itâ€™s smaller than the price on the current day, pop this index out of the stack. Repeat the same process with the new stack top.
• When the stock price that corresponds to the index at the top ofâ€‹ the stackâ€‹ is greater than the stock price of the current day, calculate the stock-span by subtracting the index at the top of the stack from the index of the current day.
1 of 22

### Example code

#include <iostream>
#include <stack>
using namespace std;

void span(int rates[], int days, int stockspan[]){

stack<int> stack; //Creating an empty stack

//Base case
stockspan[0] = 1;
stack.push(0);

for(int i=1; i<days; i++) //iterating through the rates
{
//Pop elements out of stack until either: 1) The stack gets empty
//or 2) the rate at stack top turns out to be larger than the rate
//at the current element
while(rates[i] > rates[stack.top()])
{
stack.pop();

if(stack.empty())
{
break;
}
}

//set the stockspan values.
if(!stack.empty())
{
stockspan[i] = i - stack.top();
}
else
{
stockspan[i] = i+1;
}

stack.push(i);

}
}
int main() {

int size = 6;
int rates[size] = {31,27,14,21,30,22};
int stockspan[size];

span(rates, size, stockspan);

for(int i=0; i<size; i++)
{
cout<< stockspan[i] << ", ";
}

}

RELATED TAGS

stock span
c++
python