The Stock Span Problem

It is necessary to determine the span of a stock's price throughout all n days in order to solve the stock span problem, which involves a set of n daily price quotes for a stock. The number of consecutive days soon before the given day during which the stock's price on the current day is smaller than its price on the given day is known as the span Si of the price of the stock on that day, or i.

Under the financial component, we have "The Stock Span Problem." This problem determines the stock price range for each day. Its span is the largest number of days that occur consecutively, just before a specific day, when the stock price is lower or the same as the stock price on those days.

The span Si of the stock's price on that day is defined as the maximum number of preceding days when the stock's price is less than or equal to its price on that particular day.

For instance, the span values for the seven days are 1, 1, 1, 2, 1, 4, 6 if an array of seven-day prices is given as 100, 80, 60, 70, 60, 75, and 85.

There are two approaches to solving the Stock Span problem. They are as follows:

• Inefficient approach
• Efficient approach

Navigate the input price array in the stock span problem. Increase the span value of each visited element as you traverse the left-side elements, which are smaller.

Let's now examine the Stock span issue using scripts created in C and C++ programming language.

Inefficient Approach:

C Language:

#include <stdio.h> 
void calculatetheSpan ( int rs [], int no, int Sp [] ) 
{ 
    Sp [0] = 1; 
    for ( int index = 1; index < no; index++ ) 
	{ 
        Sp [index] = 1; 
        for ( int j = index - 1; ( j >= 0 ) && ( rs [index] >= rs [j] ); j-- ) 
            Sp [index]++; 
    } 
} 
void printanArray ( int array [], int no ) 
{ 
    for ( int index = 0; index < no; index++ )  
        printf ( "%d ", array [index] ); 
} 
int main () 
{ 
    int rs [] = { 10, 4, 5, 90, 120, 80 }; 
    int no = sizeof (rs) / sizeof ( rs[0] ); 
    int Sp [no]; 
    calculatetheSpan ( rs, no, Sp ); 
    printanArray ( Sp, no ); 
    return 0; 
}  

C++ Program:

#include <bits/stdc++.h> 
using namespace std; 
void calculatetheSpan ( int rs [], int no, int Sp [] ) 
{ 
    Sp [0] = 1;  
    for ( int index = 1; index < no; index++ ) 
	{ 
 Sp [index] = 1; 
        for ( int j = index - 1; ( j >= 0 ) && ( rs [index] >= rs [j] ); j-- ) 
            Sp [index]++; 
    } 
} 
void printanArray ( int array [], int no ) 
{ 
    for ( int index = 0; index < no; index++ )  
        cout << array [index] << " ";
}   
int main () 
{ 
    int rs [] = { 10, 4, 5, 90, 120, 80 }; 
    int no = sizeof (rs) / sizeof ( rs[0] ); 
    int Sp [no]; 
    calculatetheSpan ( rs, no, Sp ); 
    printanArray ( Sp, no ); 
    return 0; 
}

Output:

1 1 2 4 5 1

The approach described above has an O(n²) time complexity. Stock span values can be computed in O(n) time.

Efficient Approach (A Linear Time Complexity Method):

C++ Program:

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


void calculatetheSpan ( int rs [], int no, int Sp [] ) 
{ 
    stack<int> stc; 
    stc.push(0); 
    Sp [0] = 1; 
    for ( int index = 1; index < no; index++ )
	 { 
        while (!stc.empty () && rs[ stc.top() ] <= rs [index]) 
            stc.pop(); 
        Sp [index] = ( stc.empty() ) ? ( index + 1 ) : ( index - stc.top () ); 
        stc.push (index); 
    } 
} 
void printanArray (int array [], int no ) 
{ 
    for ( int index = 0; index < no; index++ ) 
        cout << array [ index ] << " "; 
} 
int main () 
{ 
    int rs [] = { 10, 4, 5, 90, 120, 80 }; 
    int no = sizeof ( rs ) / sizeof( rs [0]) ; 
    int Sp [no]; 
    calculatetheSpan( rs, no, Sp ); 
    printanArray ( Sp, no ); 
    return 0; 
}

Output:

1 1 2 4 5 1

• Complexity of Time: O (n). At first glance, it appears to be larger than O(n). A deeper inspection reveals that each element of the array gets added to and removed from the stack a maximum of one time. Therefore, there are a maximum of 2n operations. We can state that the time complexity is O(n) if we assume that a stack operation takes O(1) time.
• Space Complexity: In the worst case scenario with all elements sorted in decreasing order, auxiliary space is O(n).

Another Approach: (without using stack)

C++ Program:

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


void calculatetheSpan ( int A [], int no, int ans [] )
{
	ans[0] = 1;
	for ( int index = 1; index < no; index++ ) 
	{
		int counter = 1;
		while (( index - counter ) >= 0 && A[ index ] >= A[ index - counter ]) 
		{
			counter += ans [ index - counter ];
		}
		ans [index] = counter;
	}
}
void printanArray ( int array [], int no )
{
	for ( int index = 0; index < no; index++ )
		cout << array [index] << " ";
}
int main ()
{
	int rs [] = { 10, 4, 5, 90, 120, 80 };
	int no = sizeof (rs) / sizeof ( rs [0] );
	int Sp [ no ];
	calculatetheSpan ( rs, no, Sp );
	printanArray ( Sp, no );
	return 0;
}

Output:

1 1 2 4 5 1

Another Approach: (Using Stack)

• To implement this task, we use this method, which makes advantage of the data structure stack.
• In this case, there are two stacks. While the other stack is a temporary stack, the first stack has the actual stock prices.
• The Push and Pop functions of Stack are the sole ones used to address the stock span problem.
• I've taken the array "price-rs" just to accept input values, and I've utilised the array "span" to store output.

The application of the aforementioned approach is seen below:

C Program:

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
typedef int stackentry1;
typedef struct stack
 {
	stackentry1 entry [ SIZE ];
	int top;
} STACK;
void initialisetheStack ( STACK* sp ) { sp->top = -1; }
int IsStack_full ( STACK sp )
{
	if ( sp.top == SIZE - 1 )
	{
		return (1);
	}
	return (0);
}
int IsStack_empty ( STACK sp )
{
	if ( sp.top == -1 ) 
	{
		return (1);
	}
	else {
		return (0);
	}
}
void push ( stackentry1 d, STACK* sp )
{
	if ( !IsStack_full ( *sp ) ) 
	{
		sp->entry [ ( sp -> top ) + 1 ] = d;
		sp->top = sp -> top + 1;
	}
}
stackentry1 pop ( STACK* sp )
{
	stackentry1 ans;
	if ( !IsStack_empty ( *sp ) ) 
	{
		ans = sp -> entry [ sp -> top ] ;
		sp -> top = sp -> top - 1;
	}
	else 
	{
		if ( sizeof ( stackentry1 ) == 1)
			ans = '\0';
		else
			ans = INT_MIN;
	}
	return ( ans );
}
int main ()
{
	int rs [6] = { 10, 4, 5, 90, 120, 80 };


	int span [6] = { 0 };
	int i;


	STACK sp, temp;
	initialisetheStack ( &sp );
	initialisetheStack ( &temp );
	int count = 1;
	span [0] = 1;
	push ( rs [0], &sp );
	for ( i = 1; i < 6; i++ ) 
	{
		count = 1;
		while ( !IsStack_empty (sp)
			&& sp.entry[ sp.top ] <= rs [i] )
			 {
			push( pop (&sp ), &temp );
			count++;
		}
		while ( !IsStack_empty (temp) )
		 {
			push ( pop ( &temp ), &sp ) ;
		}
		push ( rs [i], &sp );
		
		span [i] = count;
	}
	for ( i = 0; i < 6; i++ )
		printf("%d ", span[i] );
}

Output:

1 1 2 4 5 1

C++ Program:

#include <bits/stdc++.h>
using namespace std;


vector <int> calculatetheSpan ( int array [], int no )
	{
		stack<int> sp;
		vector<int> ans;
		for ( int index = 0; index < no ; index ++ )
		{
			while ( !sp.empty () and array [ sp.top() ] <= array [index]) 
						sp.pop();				
			if( sp.empty() )
				ans.push_back ( index + 1 );
			else
			{
				int top = sp.top();
					ans.push_back(index-top);
			}
			sp.push(index);
		}
	
		return ans;
	}
void printanArray ( vector<int> array )
{
	for ( int index = 0; index < array.size(); index++ )
		cout << array [index] << " ";
}
int main ()
{
	int rs [] = { 10, 4, 5, 90, 120, 80 };
	int no = sizeof (rs) / sizeof( rs [0] );
	int Sp [no];
	vector<int> array = calculatetheSpan( rs, no );
	printanArray (array);
	return 0;
}

Output:

1 1 2 4 5 1

• Time Complexity: O(n)
• Space Complexity: O(n)