Last Updated: 13 Sep, 2021

Ninjas and Levels

Moderate

Asked in company

Solve now

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].

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In this approach, we will traverse the ‘LEVELS’ array right to left and store them in an ordered set ‘LEVELSET’. Set is an inbuilt data structure implemented using Self-balancing BST that stores the elements in sorted order. Now we can use inbuilt binary search functions to find the minimum value which is greater than LEVELS[i] in this set ‘LEVELSET’. If now suitable element is found, we will set ‘ANS’[i] as -1.

At last, we will return ‘ANS’ array.

Algorithm:

Declare ‘ANS’ array of size ‘N’ to store the final answer.
Declare an ordered set ‘LEVELSET’ to store the numbers in a sorted manner.
For i in range (‘N’ -1) to 0, do the following:
- Declare ‘IDX’.
- Set ‘IDX’ as the index of the minimum value in ‘LEVELSET’ whose value is greater than ‘LEVELS[i]’ using inbuilt binary search functions.
- If ‘IDX’ is equal to the length of ‘LEVELSET’:
  - It implies that no suitable number was found.
  - Set ‘ANS’[i] as -1.
- Else:
  - Set ‘ANS’[i] as value of IDXth element in the set.
- Insert LEVELS[i] into the set.
Return ‘ANS’.

Solve now