# Span of Ninja Coin

Posted: 27 Apr, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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:

1. Make an array/list ‘RESULT’ of size ‘N’ and fill it with 0.
2. 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.
3. Return ‘RESULT’.