Last Updated: 3 Apr, 2021
NINJA'S JUMP
Hard
Asked in companies
Ninja is assigned a task to reach the last stone by his master. These stones are numbered with some value and in the form of an array. He is allowed to jump either odd-numbered jumps or even-numbered jumps and has to reach the last stone.
So your task is to find the number of starting index from which he may start jumping so he reaches the last stones. You are provided with the given array and you have to find the number of starting index of the array from which Ninja can reach the end of the array by jumping some number of times.
For jumping you have to follow below instructions:
You may jump forward from index ‘i’ to index ‘j’ (with i < j) in the following way:
During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index ‘j’ such that ‘arr[i] <= arr[j]’ and ‘arr[j]’ is the smallest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index j.
During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index ‘j’ such that ‘arr[i] >= arr[j]’ and ‘arr[j]’ is the largest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index ‘j’.
It may be the case that for some index ‘i’, there are no legal jumps.
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 contains a single integer ‘N’ denoting the size of the ‘arr’ array.
The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘arr’ array.
Output Format:
For each test case, print a single line containing the number of starting indices, from where Ninja can reach the end by following the required jump conditions.
The output of each test case will be printed 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 <= 5
1 <= N <= 5000
0 <= arr[i] < 10 ^ 6
Where ‘T’ is the number of test cases, ‘N’ is the size of an array, and ‘arr[i]’ represents the elements of the array.
Time Limit: 1 sec
Approaches
The idea here is to use the brute force approach and to travel the whole array for each index we will check if we can reach the last index of the array by following the given conditions.
- So we start from our first index and look for the elements which are greater than that element and we choose minimum from that.
- After choosing the minimum element now we check do we need an even-numbered count for reaching that element or an odd-numbered count for reaching the element.
- Now from that element, we check if we take the same jump the element is smaller than that or not.
- If it is not smaller then the index is not a good starting index.
- Else we repeat the above steps until we reach the end of the array.
- Now if we reach the end we increase our ‘ans’ variable by ‘1’.
- In this way, we checked for each index of our array.
- In the last, we return our ‘ans’ variable.
The idea here is to use the stack as we know that we want to find out the current index and the jump type whether we are taking an even jump or an odd jump. For each index, there are two options either we can make the jump or not. So if we knew these jumps, we can be able to find out the answer in a single traversal.
- Firstly we create a 2-D array ‘index’ for storing index and the value of given array as we want to do sorting so that order remains maintained.
- Now we sort our ‘index’ array and we start with storing the indices ‘i’ of the processed values v = arr[i] in the stack and try to maintain the invariant that this is monotone decreasing. Whenever we add a new index ‘j’, we pop all the smaller indices ‘i < j’ from the stack, which all jump to ‘j’.
- Then, we know ‘oddnext[i]’, the index where ‘i’ jumps to if this is an odd-numbered jump or we can say if the next possible index coming can be possible through odd jump we fill our oddnext and if comes out to be even we fill evennext.
- So we repeat the same above steps and store all the possible reachable indices.
The idea here is to use the map as a map to help in reducing the time complexity as now we think of starting from right to left and try to check by using the property of map lower_bound and upper_bound, so basically there are two functions which can be called using a map and they can tell whether the larger element is present than the element we pass in this function or smaller element is present.
- So first we declare two bool arrays ‘even’ and ‘odd’ for storing that whether we reached that index by an odd jump or even jump and we initialize our odd and even array for ‘n - 1’ as true as we reached there by both even and odd jumps.
- Now we start iterating our array and for each element, we check the lower_bound of the current element as we are traversing from right to left so to check whether the greater element is present or not.
- If it comes out true then we will check whether it is possible to go to that element using an even jump or odd jump and update our array accordingly.
- Else we repeat the same steps for the next element.
- If we reached the starting element we use upper_bound for checking whether a smaller number is present or not.
- Now we count the true in our bool array and that is our required answer,