Ninjas and Levels

Moderate

0/80

3 upvotes

Asked in company

Problem statement

All Ninjas of Ninjaland want to win more battles and level up their ninja grades. So all ninjas of Ninjaland are aligned in a line. Each ninja has a specific level. Each ninja wants to challenge a ninja having minimum level who fulfills these two conditions:

1. Ninja should be standing to the right of challenger ninja. 2. The level of ninja should be greater than the level of challenger ninja.

You are given a ‘LEVELS’ array having ‘N’ numbers. You have to print an array ‘ARR’ where ANS[i] represents the level of the ninja whom Ninja at ith place wants to challenge.If no such ninja is found ANS[i] will be -1.

For Example

For the given LEVELS = [3,5,4,6],the answer array will be [4,6,6,-1].

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’ denoting the number of Ninjas.

The second line contains ‘N’ numbers denoting the level of each ninja.

Output Format:

For each test case, print a line of ‘N’ elements corresponding to the elements of the answer array.  

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 3000.
1 <=LEVELS[i] <= 10^6

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

4 6 6 -1
3 -1 -1

Explanation of sample input 1:

For the first test case,
The Minimum number to the right of 3 which is greater than 3 is 4.
The Minimum number to the right of 5 which is greater than 5 is 6.
The Minimum number to the right of 4 which is greater than 4 is 6.
There is no number to the right of 6. So the answer will be -1.
Hence the answer is [4, 6, 6, -1].

For the second test case:
The Minimum number to the right of 1 which is greater than 1 is 3.
There is no number to the right of 3 which is greater than 3.So the answer will be -1.
There is no number to the right of 3. So the answer will be -1.
Hence the answer is [3, -1, -1].

Sample Input 2:

2
7
4 2 6 3 4 9 5  
5
7 8 10 5 10

Sample Output 2:

5 3 9 4 5 -1 -1 
8 10 -1 10 -1

Hint 1

Hint 2

Try to check all numbers situated on the right.

Approaches (2)

Approach 1

Approach 2

Brute Force

In this approach, we will first declare the answer array ‘ANS’. For each element in the ‘LEVELS’ array, we will iterate over all the elements to their right and check which element satisfies the given conditions and will update ‘ANS’ array accordingly.

Algorithm:

Declare ‘ANS’ array of size ‘N’ to store the final answer.
For each ‘i‘ in the range from 0 to ‘N’-1, do the following:
- Set ANS[i] as -1.
- For each ‘j’ in range from i+1 to ‘N’-1,do the following:
  - If ‘LEVELS’[j] > ‘LEVELS’[i]:
    - If ANS[i] is equal to -1:
      - Set ‘ANS’[i] as ‘LEVEL’[j]
    - Else:
      - Set ‘ANS’[i] as the minimum of ‘ANS’[i] and ‘LEVELS’[j].
Return ‘ANS’ array.

Time Complexity

O(N^2), where ‘N’ is the number of Ninjas.

In this approach,for each ninja,we are iterating to all the values to its right.In total there will be N*(N-1) computations.Hence the overall time complexity is O(N^2).

Space Complexity

O(1).

In this approach, we have used constant space. Hence the overall space complexity is O(1).

(100% EXP penalty)

Ninjas and Levels

Console