Understanding Stock Span

Naive Approach

Let’s look at code in C++ –

//brute force approach to find stock span values
#include <bits/stdc++.h>
using namespace std;
// function to find span of each price and stores it to array S
void calculateSpan(int price[], int n, int S[])
{
	// Span value of the first day is always 1
	S[0] = 1;
	// Find the span value of remaining days
	// by checking stock prices of previous days
	for (int i = 1; i < n; i++)
	{
		S[i] = 1; // Initializes the span[i] with 1
		// check the elements towards left until the price is less than or equal to current day’s price
        
        int j=i-1;
		while ((j >= 0) && (price[i] >= price[j]))
        {
			S[i]++;
            j--;
        }
	}
}
// function to print elements of array
void printArray(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	cout << arr[i] << " ";
}

int main()
{
	int price[] = { 10, 4, 5, 90, 120, 80 };
	int n = sizeof(price) / sizeof(price[0]);
	int S[n];
	// Calculate the span values and store in array S[]
	calculateSpan(price, n, S);
	// print the calculated span values
	printArray(S, n);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output – 

1 1 2 4 5 1

Time Complexity – 

To find the stock span of each day, we traverse at most all the elements on its left side, which is an O(n) operation. Now, we have total n elements, and to calculate each of them takes O(n) time, then total time complexity is O(n^2).

Space complexity –

It is O(n) because we use an array of size n to store the span value of each price.

Optimized Approach

Now, when n is small, then the O(n^2) algorithm may perform well, but for greater values of n, this time complexity may not be desired. 

Is there any way to optimise this approach to reduce the time complexity?

The answer is Yes. 

See, in the naive approach, we are moving towards the left of the current stock price until we find a price whose value is greater than the current price or until we reach the starting end of the array. If we preprocess the array and store the index of the closest stock price greater than the current value and which is towards the left, then our job will be done.

Let the current index be “curr”, and the closest greater element towards the left be i. So, the span will be simply equal to the number of elements between curr and i, that curr – i. 

Understand this with an example – 

Stock= [10,4,5,90,120,80]

for curr = 2, stock[curr]=5 

Nearest greater towards left = 10, whose index i =0

So, span= curr-i = 2-0=2 

Span is 2, which means for 2 days before the current day, the stock price is at most 5, 

i.e. stock prices  4 and 5 are at most 5. 

So, our goal boils down to finding the nearest greater element towards the left. 

The algorithm which we are going to learn will find that in O(n) time. 

The idea is to use a stack for this. 

Have a look at this example to understand the approach – 

n=6 Stock = [10, 4, 5, 90, 120, 80]

• Span[0] is always 1, as there are no elements towards the left of it to check.

Push the index of this element. 

The status of the stack till now is this –

• Stock[1] = 4

Compare the current value with the value at Stack[top of stack] – We find stack top i.e., 10 > 4. So, no need to pop, and we just push the index of 4 in the stack, which is 1.

Span[1]=curr-top = 1-0 = 1

Stack now – 

• Stack[2] = 5

The top of the stack is 4, which is less than 5. So, pop it. Then 10 is greater than 5. So, we stop and push the index of 5 in the stack.

Span[2] = curr-top = 2-0=2

The stack now is – 

• Stack[3]=90

Check Stack[top] i.e., Stack[2] = 5 and 5<90, pop it.

Then, stack[0]=10, and 10<90, so pop it. 

The stack becomes empty, so this means 90 is greater than all the elements towards its left. Hence, when the stack becomes empty, then the span[curr] = curr+1. 

Hence, span[3] = 3+1 = 4. (This means elements at indexes 0,1,2 & 3 all are at most current stock price)

Then we push the index of 90 that is 3.

• Stack[4] = 120

the value stack[top] = stock[3]=90 < 120. so, pop it;

Now, stack is becomes. So, span[4] = 4+1 = 5.

And then push the index of 120.

• Stack[5] = 80

Value of stack[top] = stack[4]=120 > 80. We dont pop and just push it to the stack.

Span[5] = curr-top = 5-4 = 1

C++ Implementation

// Implementation of stock span problem using stack - O(n)
#include <iostream>
#include <stack>
using namespace std;
// A stack-based efficient method to find stock span values
void calculateSpan(int price[], int n, int S[])
{
	// A stackis created and index of first element is pushed
	stack<int> st;
	st.push(0);
	// stock Span of the first day is always equal to 1
	S[0] = 1;
	// Calculate span values for the rest of the days
	for (int i = 1; i < n; i++) {
		// while the stack is not empty and top of the stack is    smaller than current price, Pop elements from the stack
		while (!st.empty() && price[st.top()] <= price[i])
			st.pop();
		// If stack becomes empty, then price[i] is
		// greater than all elements on left of it,
		// i.e., price[0], price[1], ..price[i-1]. Else
		// price[i] is greater than elements after
		// top of stack
		S[i] = (st.empty()) ? (i + 1) : (i - st.top());
		// Push the index of this element element to stack
		st.push(i);
	}
}
// Function to print elements of the array
void printArray(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	cout << arr[i] << " ";
}

int main()
{
	int price[] = { 10, 4, 5, 90, 120, 80 };
	int n = sizeof(price) / sizeof(price[0]);
	int S[n];
	// calculates the span values and stores them in S[]
	calculateSpan(price, n, S);
	// printing the calculated span values
	printArray(S, n);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output – 

1 1 2 4 5 1

Time Complexity

Every element is pushed to the stack and popped from it at most once. So, in total, we make 2n operations. Hence, the time complexity is O(2n) ⋍ O(n). 

Space Complexity – 

 As we use a stack, and size of the stack increases or decreases depending upon the value of elements. In the worst-case scenario, there can be at most n elements in the stack. This happens when the stock prices are in decreasing order. 

Like –  say Stock = [10,9,8,7,6] 

Series of operations done are – 

Push 10

10>9
Push 9

9>8
Push 8

8>7
Push 8

7>6
Push 6

Hence, the additional space complexity is O(n).

Frequently Asked Questions

Which algorithm is the most efficient for the stock span problem?

The stack-based approach is the most efficient method to solve this problem.

What is time complexity?

Time complexity denotes the time taken to solve a problem.

What is space complexity?

Space complexity is the extra space required to solve a problem.

Conclusion

In this article, we worked upon an interesting problem, Stock Span. We started with a very basic and intuitive approach and wrote a brute force algorithm as the solution. Then, we incrementally moved towards a more optimised approach and finally improved the time complexity of our solution and brought it to linear time. 

The major part of this solution depended upon another famous problem which is Nearest Greater to Left. Stacks proved to be extremely useful in reducing the time complexity in this problem. 

Read more about stacks here.