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