Last Updated: 21 Apr, 2021
Nearest Ninja
Easy
Asked in company
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.
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
Approaches
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 ‘WARRIOR_ARR[i]' > 'WARRIOR_ARR[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.
- Now run another loop from ‘j' = ‘i’ - 1 till ‘j’ is greater than or equals to ‘0’:
- In the end, return the ‘ANSWER’ array.
The idea here is to use the stack because as we know all push, pop operations take O(1) time. If the element in the stack is greater than the current element we pop the element from the stack, and if we found a smaller element we push it into the stack and also stored that index.
- Firstly we declare an array/list ‘ANSWER’ for storing our final answer.
- Create a new empty stack ‘STK’.
- Run a loop starting from ‘i' = 0 upto ‘N’ (the length of the ‘WARRIOR_ARR’).
- While ‘STK’ is nonempty and the top element of ‘STK’ is greater than or equal to 'WARRIOR_ARR[i]':
- Pop ‘STK’.
- If ‘STK’ is empty, we push ‘-1’ into ‘ANS’ as no smaller responding time is found.
- Else the nearest smaller value to 'WARRIOR_ARR[i]' is the top element of ‘STK’ push ‘WARRIOR_ARR[i]' onto ‘STK’ and ‘ANSWER[i] = i’.
- While ‘STK’ is nonempty and the top element of ‘STK’ is greater than or equal to 'WARRIOR_ARR[i]':
Similar problems