Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

stock span
c++
python

The stock span problem in C++ and Python

Educative Answers Team

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 11 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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring