# Stock Span Problem

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

1) Brute Force ApproachIn this approach, we will use the

countvariable 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:Time Complexity: O(n*n)

Space Complexity: (n)

C++ Implementation:Output2) Stack based solutionIn 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 variableflagtrue otherwise push 1 as only that element is valid and all element before is greater than it.Pseudo Code:Time Complexity for above approach: O(n)

space Complexity for above approach: O(n)

C++ Implementation:Output