Nearest Ninja

Easy
0/40
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in company
Facebook

Problem statement

Ninja and his team of 'N' warriors started a virtual way of helping each other due to lockdown. For this Ninja has arranged all the warriors linearly in the form of an array/list ‘WARRIOR_ARR’ where the index number represents the warriors (0-based indexing) and the array value represents their responding time.

To help warrior 'X' in need, Ninja decides to assign a warrior 'Y' as the helper of warrior 'X', if 'Y' has a smaller responding time than the warrior 'X' and he is in the closest position on the left side of the 'X' in the ‘WARRIOR_ARR’. If no such helper 'Y' exists (or if the responding time of all warriors is equal), Ninja will help 'X' himself and assign 'X' "-1".

As Ninja needs to be pre-prepared to assist warriors, he asks you for help. Your task is to help Ninja determine the helper 'Y' for each warrior 'X' in the 'WARRIOR_ARR'. Formally, return an array/list 'ANSWER' where 'ANSWER[i]' represents the warrior that Ninja chooses as helper of warrior at position 'i' in 'WARRIOR_ARR'.

Example : 
Suppose given ‘WARRIOR_ARR’ is [ 4, 5, 3, 7, 4 ]
So we return [ -1, 0, -1, 2, 2 ]  as ‘ANSWER’.

For the first warrior (index 0), there is no warrior with a smaller responding time on his left. So, 'ANSWER[0]' = -1.

For the second warrior (index 1), the warrior with a smaller responding time (4) and at the nearest position on the left side is at index ‘0’. So, 'ANSWER[1]' = 0.

For the third warrior (index 2), there is no warrior with a smaller responding time on his left. So, 'ANSWER[2]'  = -1.

For the fourth warrior (index 3), the warrior with a smaller responding time (3) and at the nearest position on the left side is at index '2'. So, 'ANSWER[3]' is 2.

For the fifth warrior (index 4), the warrior with a smaller responding time (3) and at the nearest position on the left side is at index '2'. So, 'ANSWER[4]' is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a ‘T’ number of test cases.

The first line of each test case contains an integer ‘N’ i.e size of the array/list ‘WARRIOR_ARR’.

The second line of each test case contains an array ‘WARRIOR_ARR’, where ‘WARRIOR_ARR[i]’ denotes the responding time of ‘i-th’ warrior.
Output Format : 
For each test case, return the ‘ANSWER’ array/list.
Note : 
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Constraints : 
1 <= ‘T’ <= 100
1 <= ‘N’ <= 10 ^ 3
1 <= ‘WARRIOR_ARR[i]’ <= 10 ^ 6

Time Limit: 1 second
Sample Input 1 :
2
7
2 6 7 4 5 6 3
5
3 6 7 8 3
Sample Output 1 :
-1 0 1 0 3 4 0
-1 0 1 2 -1
Explanation For Sample Input 1 :
Test Case 1 :
Given ‘WARRIOR_ARR’ is [ 2, 6, 7, 4, 5, 6, 3 ].
So we return [ -1, 0, 1, 0, 3, 4, 0 ]  as ‘ANSWER’.

For the first warrior (index 0), there is no warrior with a smaller responding time on his left. So, 'ANSWER[0]' = -1. 

For the second warrior (index 1), the warrior with a smaller responding time (2) and at the nearest position on the left side is at index ‘0’. So, 'ANSWER[1]' = 0.

For the third warrior (index 2), the warrior with a smaller responding time (6) and at the nearest position on the left side is at index ‘1’. So, 'ANSWER[2]' = 1.

For the fourth warrior (index 3), the warrior with a smaller responding time (2) and at the nearest position on the left side is at index ‘0’. So, 'ANSWER[3]' = 0.

For the fifth warrior (index 4), the warrior with a smaller responding time (4) and at the nearest position on the left side is at index ‘3’. So, 'ANSWER[4]' = 3.

For the sixth warrior (index 5), the warrior with a smaller responding time (5) and at the nearest position on the left side is at index ‘4’. So, 'ANSWER[5]' = 4.

For the seventh warrior (index 6), the warrior with a smaller responding time (2) and at the nearest position on the left side is at index ‘0’. So, 'ANSWER[6]' = 0.


Test Case 2 :
Given ‘WARRIOR_ARR’ is [ 3, 6, 7, 8, 3 ].
So we return [ -1, 0, 1, 2, -1 ]  as ‘ANSWER’.

For the first warrior (index 0), there is no warrior with a smaller responding time on his left. So, 'ANSWER[0]' = -1. 

For the second warrior (index 1), the warrior with a smaller responding time (3) and at the nearest position on the left side is at index ‘0’. So, 'ANSWER[1]' = 0.

For the third warrior (index 2), the warrior with a smaller responding time (6) and at the nearest position on the left side is at index ‘1’. So, 'ANSWER[2]' = 1.

For the fourth warrior (index 3), the warrior with a smaller responding time (7) and at the nearest position on the left side is at index ‘2’. So, 'ANSWER[3]' = 0.

For the fifth warrior (index 4), there is no warrior with a smaller responding time on his left. So, 'ANSWER[4]' = -1.
Sample Input 2 :
2
7
2 5 1 4 8 3 2
5
5 4 3 2 1
Sample Output 2 :
-1 0 -1 2 3 2 2
-1 -1 -1 -1 -1
Hint

Can you think of traversing the left side of each element?

Approaches (2)
Brute Approach

The idea here is to use the brute force approach.

 

For each index, we traverse in the left side of the ‘WARRIOR_ARR’ starting from that index, and if we find a smaller element, we store its index in ‘ANSWER’. Else we store ‘-1’ for that element.

 

  • Firstly, we declare an array named ‘ANSWER’ for storing our final answer and store  ‘-1’ as for the first element as there is never a smaller element on the left side of ‘WARRIOR_ARR[0]’.
  • Run a loop starting from ‘i' = 1  up to ‘N’:
    • Now run another loop from ‘j' = ‘i’ - 1 till ‘j’ is greater than or equals to ‘0’:
      • If ‘WARRIOR_ARR[i]' > 'WARRIOR_ARR[j]’:
        • ‘ANSWER[i]' = 'j’
    • If ‘j’ = -1, then ‘ANSWER[i]’ = -1. It implies there exists no warrior on the left of warrior 'i' with a smaller responding time.
  • In the end, return the ‘ANSWER’ array.
Time Complexity

O(N ^ 2), where ‘N’ is the size of the given ‘WARRIOR_ARR’ array.

 

As for each and every element, we are traversing the whole array and in the worst case, we have to travel the whole array for each index.

Space Complexity

O(N), where ‘N’ is the size of the given ‘WARRIOR_ARR’ array.

 

As we are using an ‘ANSWER’ array for storing the index.

Code Solution
(100% EXP penalty)
Nearest Ninja
Full screen
Console