Home » Interview coding problems/challenges

Stock Span Problem

Stock Span Problem: Here, we are going to find the solution of Stock Span Problem using Stack and Brute Force Approach – which has been featured in coding interviews of many top companies such as Goldman sachs, Amazon, Factset, DE-Shaw etc. Submitted by Divyansh Jaipuriyar, on May 04, 2020

Problem statement

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate the span of stock's price for all n days.

The span Si of the stock's price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}.

Input

The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N, N is the size of the array. The second line of each test case contains N input arr[i].

Output

For each testcase, print the span values for all days.

Examples:

    Input:	
    T = 1
    N = 6
    [10, 4, 5, 90, 120, 80]
    
    Output: 
    1 1 2 4 5 1

    Input:
    T = 1
    N = 7
    [2,4,5,6,7,8,9]
    
    Output: 
    1 2 3 4 5 6 7

Solution Approach

1) Brute Force Approach

In this approach, we will use the count variable for each element and check all the elements before it, if the elements are smaller than or equal to the current element then increase the count variable.

We will store each element's count in a vector and then print the elements.

This approach will traverse the elements in the entire array hence time complexity will be O(n*n).

Pseudo Code

function(arr[],n):
	//vector to store the elements which are <= to current element.
	vector<int>v1

	//1st element is always 1 as there is no other element 
	v1.push_back(1)
	for(int i=1;i<n;i++)
		cnt=1;
	// Traverse left while the next element   
	// on left is smaller than price[i]  
	for(int j = i - 1; (j >= 0) &&  (arr[i] >=arr[j]); j--)
		cnt++;
		v1.push_back(cnt);

	for(int i=0;i<n;i++) //print the results.
		cout<<v1[i]<<" ";
	
	return 0;

Time Complexity: O(n*n)
Space Complexity: (n)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n; //size of stock array variable.
        cout << "Enter size of stock's price array: ";
        cin >> n;

        ll arr[n];

        cout << "Enter stock prices: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
        vector<ll> v1;
        v1.push_back(1);
        for (ll i = 1; i < n; i++) {
            ll cnt = 1;
            //compare smaller index before current index and check the condition.
            for (ll j = i - 1; (j >= 0 and arr[j] <= arr[i]); j--) 
                cnt++;
            v1.push_back(cnt);
        }

        cout << "Span Values: "; //print then span values.
        for (ll i = 0; i < n; i++)
            cout << v1[i] << " ";
        cout << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of stock's price array: 5
Enter stock prices: 1 2 5 9 2  
Span Values: 1 2 3 4 1 
Enter size of stock's price array: 9
Enter stock prices: 1 2 3 4 5 6 7 8 9
Span Values: 1 2 3 4 5 6 7 8 9 
Enter size of stock's price array: 7       
Enter stock prices: 100 99 98 97 96 95 94
Span Values: 1 1 1 1 1 1 1 

2) Stack based solution

In this approach we will use stack with pair, we will store array element and its index, each time we iterate through array element. We check the previous next greater element, it the previous greater element is found at some location i, then we will take the difference between the current index element and the previous greater element.

We will use a vector for each index to push the number of elements that are smaller than or equal to the current element.

We will use a boolean variable flag, if the element is pushed according to condition then make variable flag true otherwise push 1 as only that element is valid and all element before is greater than it.

Pseudo Code

function(arr[],n):
	//initialise vector for resulst.
	vector<int>v1
	//initialise stack variable.
	stack<pair<int,int>>st
	//put maxm value of int with index -1 if there is no element 
	//is present which are greater than current element 
	//then this will work.
	st.push({INT_MAX,-1})

	for(int i=0;i<n;i++)
	{
		//initialse boolean flag variable as false.
		bool flag=false
		while(!st.empty())
		{
			//compare with top element of the stack which are before array.
			if(st.top().first>arr[i]) 
			{
				v1.push_back(i-st.top().second)
				flag=true
				break
			}
			else
				//if current top element is smaller than pop top element.
				st.pop()    
		}
		if(flag==false)
			v1.push_back(1)
		//push current element and its index.
		st.push({arr[i],i})
	}
	// print the values of span.
	for(int i=0;i<n;i++)  
		cout<<v1[i]

Time Complexity for above approach: O(n)
space Complexity for above approach: O(n)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n; //size of stock array variable.
        cout << "Enter size of stock's price array: ";
        cin >> n;

        ll arr[n];

        cout << "Enter stock prices: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
        stack<pair<ll, ll> > st; //stack declaration.
        st.push({ INT_MAX, -1 });
        vector<ll> v1;
        for (ll i = 0; i < n; i++) {
            bool flag = false;
            while (!st.empty()) {
                // is stack top is greater than current element then
                // put the difference value in the vector.
                if (st.top().first > arr[i]) 
                {
                    v1.push_back(i - st.top().second);
                    flag = true;
                    break;
                }
                else
                    st.pop(); //if top value is not greater than pop.
            }
            if (flag == false)
                v1.push_back(1);
            st.push({ arr[i], i });
        }
        cout << "Span Values: "; //print then span values.
        for (ll i = 0; i < n; i++)
            cout << v1[i] << " ";
        cout << "\n";
    }
    return 0;
}

Output

Enter number of test cases: 3
Enter size of stock's price array: 5
Enter stock prices: 2 5 9 1 2 
Span Values: 1 2 3 1 2 
Enter size of stock's price array: 7
Enter stock prices: 100 80 60 70 60 75 85
Span Values: 1 1 1 2 1 4 6 
Enter size of stock's price array: 9
Enter stock prices: 1 2 3 4 5 6 7 8 9
Span Values: 1 2 3 4 5 6 7 8 9 

Problem reference: https://leetcode.com/problems/online-stock-span/