Understanding the Stock Span Problem

Table of Contents

Introduction

We all have come across the terms of e-trading, stocks, etc., right? Well, here this time we have kind of the same problem although don’t worry we won’t be dealing with trading algorithms or that sort. This stock span problem suggests that suppose we are given an array that contains n daily prices of a stock and we have to find out the span of the current stock’s price.

The Span of current stock is basically the number of days prior to the current day where the price of that sock was lesser or equal to the current stock. Well, for the basic approach we do not need any prerequisite but for the efficient approach of this solution, we require stacks.

Naive Approach

In this problem as we have seen earlier, we just have to find out how many such consecutive days are there prior to the current day where the price of the stock was lesser or equal. Let us see an example.

Taking one example of let Day 6 where the price is 75. For this day there are 3 more days where the price has been less – Day 5, 4, 3, and 6 itself. Hence the span of this stock at 6^th day is 4.

The naïve approach will be to iterate over the day array for every day, and find out the nearest greatest index to the left where the price is greater than the current index.

Let this nearest greatest index to the left is called NGL. Let us see the code implementation:

#include <bits/stdc++.h>
using namespace std;
void stock_span(int *day,int n){
	int *ans = new int[n];
	memset(ans,0,n);
	ans[0] = 1;
	for(int i = 1;i<n;i++){
		//i is the current day
		int j = i-1; //starting from just left of current index
		//to find the NGL index
		while(j>=-1){
			if(day[j] > day[i])
				break;
			j--;
		}
		//j will contain the NGL if j!=-1
		if(j!=-1)ans[i] = (i - j);
		// NGL - curr_idx will give the current span for the stock
		else ans[i] = i+1;
	}
	for(int i= 0 ;i<n;i++)cout<<ans[i]<<" ";
}
int main() {
	// your code goes here
	int n;
	cin>>n;
	int *day = new int[n]; //day stock price 
	for(int i = 0;i<n;i++)cin>>day[i];
	stock_span(day,n);
	return 0;
}

Time Complexity: Where n is the number of elements in the day array.
Space Complexity: Only for the extra answer array which can be easily eliminated.

Now let us revisit Stack as it will be necessary for our next approach i.e. the more efficient one.

Stack

This is a popular and very useful data structure that works on the method of Last In First Out(LIFO). It takes in data as a series of inputs and fills the memory space one above another just like a stack of books. It has a top pointer that is used to insert as well as remove elements from the top. Here we will just see the STL version of a stack in our implementation.

When we insert an element, the top pointer is incremented and then the new element id inserted while when we are removing an element the top pointer is decremented. We will be using this stack data structure in our next efficient method. It can be represented using arrays, linked list, queue etc. Here I have discussed only the Linked List Representation.

Code Linked List Representation

struct stack{
	int data;
	stack *next;
}; //structure of stack
struct stack *createstack(){return NULL;}
void push(struct stack **top, int data){
//adding data to top of stack
	struct stack *temp;
	temp = new stack;
	temp->data = data;
	temp->next = *top;
	*top = temp;
}
int pop(struct stack **top){
//Removing data from top of stack
	int data;
	struct stack *temp;
	temp = *top;
	*top = *top->next;
	data = temp->data;
	free(temp);
	return data;
}

Linear Time Approach

There is another way of reducing the time complexity of this problem. The idea is to store that index preceding the current index where the value of the stock is greater and hence by this, we can directly get the span by simply subtracting that from our current index. If such a day does not exist, we will simply call it -1. The approach is to store the current index of those elements in the stack having day price value greater than the current index, i.e. having only the NGL values for a current index.

Code Implementation

#include <bits/stdc++.h>
using namespace std;
void stock_span_n(int *day,int n){
		int *ans = new int[n];
	memset(ans,0,n);
	stack<int> s;
	s.push(0); //pushing the 0th index into the stack
	ans[0] = 1; //span of first element is 1
	for(int i = 1;i<n;i++){
		while (!s.empty() && day[s.top()] <= day[i]) 
		//pop the stack until all the elements in the stack has smaller values than current
		//when this loop breaks and we are at some index that index will refer to our NGL
            s.pop();
        if(s.empty())
        	ans[i] = i+1;
        else
        	ans[i] = i - s.top(); //s.top() acts as the NGL
        s.push(i);
	}
	for(int i= 0 ;i<n;i++)cout<<ans[i]<<" ";
}
void stock_span(int *day,int n){
	int *ans = new int[n];
	memset(ans,0,n);
	ans[0] = 1;
	for(int i = 1;i<n;i++){
		//i is the current day
		int j = i-1; //starting from just left of current index
		//to find the NGL index
		while(j>=-1){
			if(day[j] > day[i])
				break;
			j--;
		}
		//j will contain the NGL if j!=-1
		if(j!=-1)ans[i] = (i - j);

		// NGL - curr_idx will give the current span for the stock
		else ans[i] = i+1;
	}
	for(int i= 0 ;i<n;i++)cout<<ans[i]<<" ";
}
int main() {
	// your code goes here
	int n;
	cin>>n;
	int *day = new int[n]; //day stock price 
	for(int i = 0;i<n;i++)cin>>day[i];
	stock_span_n(day,n);
	return 0;
}

Time Complexity: Where n is the number of days – array.
Space Complexity: Where n for the stack we have used.

Conclusion

This stock span problem is quite popular in interviews and a wide variety of questions are asked from this. The initial naïve way is quite easy to understand as it is intuitive although the application of stack is quite interesting here and we can get a slight idea of where we can actually use stacks.

Hope this problem is now clear to understand and it helps aspiring developers and programmers. You can check out our YouTube channel for more insights or visit our website.

By Aniruddha Guin