Online Stock Span

PROBLEM STATEMENT

Ninja Coin is a famous crypto-currency in Ninja Land. Ninja has an array/list ‘PRICE’ of size ’N’ where ‘PRICE[i]’ is the price of a Ninja Coin on an ith day in INR, where 0 <= 'i' <= N-1.

The span of the Ninja Coin price on an ith day is defined as the maximum number of consecutive days (starting from the ith day and going backward) for which the price of a Ninja Coin was less than or equal to its price at ith day.

Your task is to return an array/list of size ‘N’ where the ith integer is the span of Ninja Coin price on an ith day. Go through the example for more clarity.

For Example :

Let the price of Ninja Coin for 5 consecutive days is [4, 2, 3, 3, 7].

Then the span of Ninja Coin on the 0th day is 1 because we cannot move backward from day 0.

The span of Ninja Coin on the 1st day is 1 because the price on day 0 is 4 which is greater than 2, so the only day 1 is counted.

The span of Ninja Coin on the 2nd day is 2 because the price on day 2 and day 1 is less than or equal to 3 and then on day 0 price is 4 which is greater than 3, so we count day 2 and day 1.

The span of Ninja Coin on the 3rd day is 3 because the price on day 3, day 2, and day 1 is less than or equal to 3, and on day 0 price is 4 which is greater than 3, so we count day 3, day 2, and day 1.

The span of Ninja Coin on the 4th day is 5 because its value is higher than all previous days values.    

Thus you should return an array/list [1, 1, 2, 3, 5].

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case will contain a single integer ‘N’, representing the size of ‘PRICE’ 

The second line of each test case will contain ‘N’ space-separated integers representing array/list ‘PRICE’.

Output Format :

For each test case, return an array/list containing ‘N’ integers where the ith integer is the span of Ninja Coin price on an ith day, where 0 <= 'i' <= N-1.

Output for every test case will be printed in a separate line.

Note :

You don’t need to print anything. It has already been taken care of.

Constraints :

1 <= T <= 50
1 <= N <= 10000
1 <= PRICE[i] <= 10^9


Where ‘T’ is the number of test cases, 'N' is the size of ‘PRICE’, ‘PRICE[i]’  is the price of a Ninja Coin on an ith day in INR.


Time limit: 1 sec.

Approach 1

The basic idea is to make an array/list ‘RESULT’ of size ‘N’ and fill it with 0, then for each ‘i’ (0 <= ‘i’ < ‘N’) we iterate backward from ‘i’, using pointer ‘j’ till PRICE[j] <= PRICE[i] and increment RESULT[i] by 1 for each such ‘j’.

Algorithm:

Make an array/list ‘RESULT’ of size ‘N’ and fill it with 0.
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and do the following -:
1. Initialize an integer ‘j’ := ‘i’.
2. Run a loop till ‘j’ >= 0 and PRICE[j] <= PRICE[i]:
  1. Increment ‘RESULT[i]’ by 1,
  2. Decrement ‘j’ by 1.
Return ‘RESULT’.

Try Problem

Approach 2

The basic idea is to use a stack here. We can track all the days before ‘i’ which has a Ninja Coin price higher than its price at day ‘i’ in increasing order of price from top to bottom. Using this stack we can find the span at any day ‘i’ in O(1) time.

Algorithm:

Make an array/list ‘RESULT’ of size ‘N’ and fill it with 0.
Create an empty stack ‘STK’.
Run a loop where ‘i’ ranges from 0 to ‘N’-1 and do the following -:
1. Run a loop till ‘STK’ is not empty and PRICE[STK.top()] <= PRICE[i] -:
  1. Pop-top element from STK.
2. If ‘STK’ is empty, then do ‘RESULT[i]’:= i+1, otherwise do RESULT[i] = i - STK.top(), Where STK.top() is the top element of stack.
3. Push ‘i’ in STK.
Return ‘RESULT’.