The Stock Span Problem is one of the famous financial problems where we have a list of prices of stocks of consecutive n days and we have to calculate the span of stock’s price for all the n days. The span of a particular day is defined as a maximum number of consecutive days before the day, for which the price of the stock on a particular day is less than or equal to the current day.
For Example :
Consider an array containing the price of sock for the 7 consecutive days .{200,60,140,120,150,170}, the span of these stocks for particular days will be {1,1,1,2,1,4, 6 }.
Input: {100,80,60,70,60,75}
Output: {1,1,1,2,1,4 }
Approach: (Naive Approach)
- This is a simple approach to solve this problem where we use two nested loops and check the price of all consecutive days before the current days.
- Calculate the consecutive number of days on which the price of the stack is smaller or equal to the current day’s stock price.
- Store the count of the number of days in an array or list.
- Return the array/List.
Java Programming
//Importing libraries
import java.util.*;
import java.io.*;
//Main class
class Main1{
//Function to print the span details of the stock
static void print(int span[]){
for(int details_:span){
System.out.print(details_+" ");
}
}
//Function to calculate the stock span
static int [] calulate_stockspan(int price_stock[],int length){
//Checking the base condition
if(length==0){
return null ;
}
//Creating an array to store the details of the stock
int span[]=new int[length];
//Minimum span will be 1
Arrays.fill(span, 1);
for(int i=0;i<price_stock.length;++i){ int count=1; for(int j=i-1;j>=0;--j){
//Checking the condition of the stock
if(price_stock[j]<=price_stock[i]){
//Increment the value
++count;
}
else{
break;
}
}
//Store the details of the span
span[i]=count;
}
//Return the span details
return span;
}
public static void main(String args[]){
//Array containing stock price
int price_stock[]={100,80,60,70,60,75};
//Length of the array
int length=price_stock.length;
//Function to calculate the span
int span[]=calulate_stockspan(price_stock, length);
//Print the span details
System.out.println("Stock_Span");
print(span);
}
}
Output:
Python Programming
#Function to calculate the span details
def calulate_stockspan(price_stock,length):
#Checking the base condition
if(length==0):
return 0
else:
span=[]
for i in range(len(price_stock)):
count=1
j=i-1
while j>=0:
#Checking the condition of the stock
if(price_stock[j]<=price_stock[i]):
#Increment the value
count=count+1
else:
break
j=j-1
#Insert the count
span.insert(i,count)
#Return the span details
return span
def main():
#List containing stock price
price_stock=[100,80,60,70,60,75]
#Length of the list
length=len(price_stock)
print("Printing the details of the span")
span=calulate_stockspan(price_stock, length)
print(span)
main()
Output:
C++ Programming
//Importing the libraries
# include<iostream>
# include <conio.h>
#include <bits/stdc++.h>
using namespace std;
//Function to calculate the span of the stock price on a particular day
void calulate_stockspan(int price_stock[],int length,int span[]){
//Checking the base condition
if(length==0){
return ;
}
for(int i=0;i<length;++i){ int count_=1; for(int j=i-1;j>=0;--j){
//Checking the condition of the stock
if(price_stock[j]<=price_stock[i]){
//Increment the value
++count_;
}
else{
break;
}
}
//Store the details of the span
span[i]=count_;
}
//Return the span details
}
void print(int span[],int length){
for(int i=0;i<length;++i){
cout<<span[i]<<" ";
}
}
int main(){
//Array containing stock price
int price_stock[]={100,80,60,70,60,75};
//Length of the array
int length=sizeof(price_stock)/sizeof(price_stock[0]);
//Creating an array to store the details of the stock
int span[length];
//Function to calculate the span
calulate_stockspan(price_stock, length,span);
//Print the span details
printf("%s\n","Printing Spanning details");
print(span,length);
return 0;
}
Output:
Complexity :
- Time Complexity : The Time complexity of this approach is O(n^n).
- Space Complexity : The Space Complexity of this approach is O(n).
Approach 2: (Optimised Approach)
- In this approach, we will use the stack data structure because of the LIFO property, which is the “Last in First out” of the stack data structure .
- Pop all indexes from the stack until the current index stock price becomes smaller than the upcoming index value from the stack.
- Check two conditions, if the stack is empty, the answer will be current index value+1.
- Otherwise, the answer will be the current index-peak element of the stack(span of stock).
- Push the current index into the stack.
C++ Programming
//Importing the libraries
# include <conio.h>
# include <iostream>
#include <bits/stdc++.h>
using namespace std;
//Function to calculate the span of the stock price
void calulate_stockspan(int price[],int length){
//Creating stack to store the index of the stock price
stackst;
//Creating Vector to store the span of particular price
vectorvc;
for(int i=0;i<length;++i){
//Checking the condition
while(!st.empty()&&(price[st.top()]<=price[i])){
//pop the element
st.pop();
}
//Checking if stack is empty or not
if(st.empty()){
//push the index into the vector
vc.push_back(i+1);
//Push the index of the current element into the stack
st.push(i);
}
else{
vc.push_back(i-st.top());
//Push the index of the current element into the stack
st.push(i);
}
}
//Print the span details
printf("%s\n","Printing Span details");
for(int i=0;i<length;++i){
//Printing the span details of the stock price
cout<<vc[i]<<" ";
}
}
int main(){
//Array containing stock price
int price_stock[]={100,80,60,70,60,75};
//Length of the array
int length=sizeof(price_stock)/sizeof(price_stock[0]);
//Function to calculate the span
calulate_stockspan(price_stock, length);
return 0;
}
Output:
Java Programming
//Importing the libraries
import java.util.*;
//Creating class
class Main1{
//Function to print the span details of the stock
static void print(int arr[]){
for(int i=0;i<arr.length;++i){
//Printing the span details
System.out.print(arr[i]+" ");
}
}
//Function to calculate the span details of the stock price
static int [] span(int arr[],int length){
//Creating stack to store the minimum stock price
StackS=new Stack();
//Creating array to store the span details
int span[]=new int[length];
for(int i=0;i<length;++i){
//Checking the condition
while(!S.empty()&& arr[S.peek()]<=arr[i]){
//Pop the index from the array
S.pop();
}
//Checking the condition
if(S.empty()){
//Push the element into the stack
S.add(i);
//Update the array
span[i]=i+1;
}
else{
span[i]=i-S.peek();
S.add(i);
}
}
//Return the span array
return span;
}
public static void main(String args[]){
int arr[]={100,80,60,70,60,75,85};
int length=arr.length;
//Call function to calculate the span details of the stock price and returning the array
int span[]=span(arr,length);
System.out.println("Printing the Span Details");
print(span);
}
}
Output:
Python Programming
#Function to calculate the span details
def calulate_stockspan(price_stock,length):
#Checking the base condition
if(length==0):
return 0
else:
st=[]
#List for storting the span details
span=[]
for i in range(len(price_stock)):
#Pop the elements from the stack until the condition is true
while(len(st)>0 and price_stock[st[-1]]<=price_stock[i]):
st.pop()
#Checking the base condition
if(len(st)==0):
#Append the new element details
span.append(i+1)
st.append(i)
else:
span.append(i-st[-1])
st.append(i)
#Return the span details
return span
def main():
#List containing stock price
price_stock=[100,80,60,70,60,75]
#Length of the list
length=len(price_stock)
print("Printing the details of the span")
span=calulate_stockspan(price_stock, length)
print(span)
main()
Output:
Complexity :
- Time Complexity : The Time complexity of this approach is O(n).
- Space Complexity : The Space Complexity of this approach is O(n).
Approach 3: (Recursive Approach)
- In this approach, we use simple recursion to calculate the stock span of every stock price of a particular day.
- Iterate a loop and call a recursive function to all previous indexes and count the total number of days for which the price of the current element is larger or equal to all previous consecutive days.
- Store the count in an array.
- Return the array. The array will contain all the span details of all the stock prices.
Java Programming
//Importing libraries
import java.util.*;
import java.io.*;
//Main class
class Main1{
//Function to print the span details of the stock
static void print(int span[]){
for(int details_:span){
//Printing the stock span
System.out.print(details_+" ");
}
}
static int span_recursive(int previous_index,int starting_index,int price_stock[],int price){
//Checking base condition
if(previous_index<0){ return 0; } //Checking the price of previous day stock if(price_stock[previous_index]>price){
return 1;
}
//Call next previous day stock
int span=1+ span_recursive(previous_index-1, starting_index, price_stock, price);
//Return the answer
return span;
}
//Function to calculate the stock span
static void calulate_stockspan(int price_stock[],int length,int starting_index,int span[]){
for(int i=starting_index;i<length;++i){
//Call recursive function to calculate individual stock span
int ans=span_recursive(i-1,i,price_stock,price_stock[i]);
span[i]=ans;
}
}
public static void main(String args[]){
//Array containing stock price
int price_stock[]={100,80,60,70,60,75};
//Length of the array
int length=price_stock.length;
int span[]=new int[length];
//Function to calculate the span
calulate_stockspan(price_stock, length,1,span);
//Print the span details
System.out.println("Printing stock span details");
span[0]=1;
print(span);
}
}
Output:
C++ Programming
//Importing the libraries
# include <iostream>
#include <bits/stdc++.h>
using namespace std;
int span_recursive(int previous_index,int starting_index,int price_stock[],int price){
//Checking base condition
if(previous_index<0){ return 0; } //Checking the price of previous day stock if(price_stock[previous_index]>price){
return 1;
}
//Call next previous day stock
int span=1+ span_recursive(previous_index-1, starting_index, price_stock, price);
//Return the answer
return span;
}
//Function to calculate the span of the stock price on a particular day
void calulate_stockspan(int price_stock[],int length,int starting_index,int span[]){
for(int i=starting_index;i<length;++i){
//Call recursive function to calculate individual stock span
int ans=span_recursive(i-1,i,price_stock,price_stock[i]);
span[i]=ans;
}
}
void print(int span[],int length){
for(int i=0;i<length;++i){
cout<<span[i]<<" ";
}
}
int main(){
//Array containing stock price
int price_stock[]={100,80,60,70,60,75};
//Length of the array
int length=sizeof(price_stock)/sizeof(price_stock[0]);
//Creating an array to store the details of the stock
int span[length];
//Function to calculate the span
calulate_stockspan(price_stock, length,1,span);
//Print the span details
printf("%s\n","Printing Spanning Values");
span[0]=1;
print(span,length);
return 0;
}
Output:
Python Programing
#Function to calculate the span details
def span_recursive(previous_index, starting_index, price_stock, price):
#Checking the base condition
if(previous_index<0): return 0 if(price_stock[previous_index]>price):
return 1
#Call to the previous day for the span
return 1+span_recursive(previous_index-1,starting_index,price_stock,price)
#Function to calculate the span of the stock
def calulate_stockspan(price_stock, starting_index,length, span):
i=starting_index
while(i<length):
#Recursively call previous day
ans=span_recursive(i-1,i,price_stock,price_stock[i])
span.append(ans)
i=i+1
def main():
#List containing stock price
price_stock=[100,80,60,70,60,75]
#Length of the list
span=[]
length=len(price_stock)
print("Printing the details of the span")
calulate_stockspan(price_stock, 1,length,span)
print(span)
main()
Output :
Complexity
:
- Time Complexity : The Time complexity of this approach is O(n^n).
- Space Complexity : The Space Complexity of this approach is O(n).
Conclusion
The Stock Span Problem is one of the most interesting problems of Data structure. In this article, we have discussed three approaches to solve The Stock Span Problem. One is the naive approach, the next one is the recursive implementation of the naive approach, and the third one is the optimized approach of this problem using the stack data structure. There are so many variations that can be made from this problem and this problem is most commonly asked during technical interviews. We hope this article will help you to understand the problem statement and you will be able to solve any other variation of this problem. Happy Coding! People are also reading:
Leave a Comment on this Post