Table of Contents
Introduction
Let’s start with reading the problem statement of Stock Span –
You are given a list of stock prices of “n” days, and you need to find the span of each stock’s price for all the “n” days.
Consider an array of stock prices given to us –
Let n=7 and array be Stock = [100, 80, 60, 70, 60, 75, 85].
For every Stock[i], where i varies from 0 to n-1, you have to find its span.
What is the meaning of the stock span of a particular Stock[i]?
It is equal to the maximum number of consecutive days before(including the current day) for which the stock price for each of those days is at most the present day’s stock price. This means that for each of those stock prices, p, p is less than or equal to the current day’s price.
Before moving on to the solution, please try to solve the Stock span problem here by yourself.
In the above array –
for i=0, Stock[0] = 100 initialise span[0]=1 Since this is the first day, i.e. we don't have any stock prices to check before it, its span is equal to 1. for i=1, Stock[1] = 80 initialise span[1]=1 We will look for the prices before index 1. Stock[0]=100, which is greater than 80 so, we don't move any further as we need them to be consecutive. Span = 1 for i=2, Stock[2]=60 initialise span[2]=1 before this, we have - 100,80 now 80 > 60, we stop checking further and hence span = 1. for i=3, Stock[3] = 70 initialise span[3]=1 before this, we have - 100,80,60 60<70, so we increment span[3] by 1, which becomes 2. 80>70. So, we stop. for i=4, Stock[4] = 60 initialise span[4]=1 before this, we have - 100,80,60,70 70 > 60, so stop for i=5, Stock[5] = 75 initialise span[5]=1 before this, we have - 100,80,60,70,60 60<75, so increase span[5] by 1, making it equal to 2. 70<75, again do span[5] = span[5]+1 = 2+1 = 3 60<75, do span[5] = span[5]+1 = 3+1 = 4 80>75, so we stop. for i=6, Stock[6] = 85 initialise span[6]=1 before this, we have - 100,80,60,70,60,75 75<85, do span[6]= span[6]+1 = 1+1=2 60<85, do span[6]= span[6]+1 = 2+1=3 70<85, do span[6]= span[6]+1 = 3+1=4 60<85,do span[6]= span[6]+1 = 4+1=5 80<85,do span[6]= span[6]+1 = 5+1=6 100 > 85 , so stop.
So, with this, we get our Span array as –
Span = [1,1,1,2,1,4,6]
The approach we followed to find the stock span of each stock price is a simple brute force method.
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;
}
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;
}
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).
Key Takeaways
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.
By: Yukti Kumari
