Logo
×

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(n2) 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)

Related Topics

How to Setup Environment for C++ Programming on Mac

Mac OS X code Installation There are so many environments available for C++. We are going to install jGrasp and Xcode in our mac operating system. Instruction for installation of jGrasp and...

2 minutes read.

Difference between "int main( ) and int main(void)" in C/C++

int main( ) function In the C/C++ programming language, int main() indicates a function that returns an integer at the end of the program execution. In general, a value of '0' indicates...

3 minutes read.

C++ Virtual Function

A virtual function is such function which is declared inside the base class and redefined by the derive class. C++ uses a virtual keyword to make a function as a virtual function. The virtual...

1 minute read.

C++ Recursion Function

A programming method called recursion that uses a function to call itself to address lesser problems. The Fibonacci sequence, factorial computation, and tree traversal are just a few of the...

4 minutes read.

This keyword in C++

This keyword in C++ is a pointer which points to the object. It is passed as an argument to functions which helps in accessing the object. It is used for a...

3 minutes read.

4 Pillars of OOPs

OOPs OOPS means Object Oriented Programming System Structure. Object oriented Programming is defined as an approach that provides a way of modularizing programs by creating partitioned memory area for both data...

11 minutes read.

C++ Range-based For Loop

In C++ language, the range-based for loop was added, which is far superior than the ordinary For loop. The implementation of a range-based for loop doesn't really need much code. It's a...

4 minutes read.

Naming Convention in C++

The first and most fundamental step a programmer takes to produce clean code is to name a file or a variable. This naming must be acceptable so that it serves...

5 minutes read.

C++ Continue in for loop

Continue statement: Inside the loop, the continue statement is used to control the loop. C++ utilizes the continue keyword to implement the continue statement, which transfers the program's flow at the start...

4 minutes read.

Do-While Loop Examples in C++

Before we move on the examples of Do-While loop, let’s learn little bit about the Do-While loop in C++ language. Do While loop An iterative loop that checks the condition at the...

5 minutes read.

SDL library in C++ with Examples

SDL stands for Simple DirectMedia Layer. Using OpenGL and Direct3D, it is a cross-platform development library created to give users low-level access to audio, keyboard, mouse, joystick, and graphics hardware....

3 minutes read.

C++ Queue

C++ queue: Queue in C++ is also a container adapter with the functionality of a queue. Queue is just the opposite of the stack in C++ because stack works on...

4 minutes read.

Auto keyword in C++

The primary function of auto keyword is to assign and detect the value of the data type automatically in C++. The compiler knows the data type of the variable by...

2 minutes read.

Advanced C++ with Boost Library

The goal of the Boost Libraries is to be widely applicable and used in a variety of applications. For instance, they can in handy when working with huge numbers whose...

4 minutes read.

Division in C++

C++ Division Arithmetic Operation In C++ the arithmetic operator / is used for division. This operator takes two operands and returns the result of dividing the left operand by the right...

3 minutes read.

C++ String Concatenation

C++ String Concatenation In this section, we will learn about C ++ String Concatenation, what it does, how it works, and will also see its programs. What is the String Concatenation? The + operator...

3 minutes read.

Ascending order in C++

In C++, the term "ascending order" refers to a specific order in which a list of elements is arranged. When a list of elements is arranged in ascending order, the...

3 minutes read.

C++ Inheritance

What do you mean by Inheritance ? The ability to define new classes based on existing classes in order to reuse and organise code is referred to as inheritance. Single inheritance...

7 minutes read.

Substring in C++

A substring is a function in c++ that is imported from the string library. An element of a string is called a substring. A substring contains two parameters length and...

2 minutes read.

C++ Global Variable

In C++, a global variable is a variable that is defined outside of any function or class and can be accessed by any function or class in the program. Global...

4 minutes read.