Online Stock Span

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.