Minimum Number of Jumps to reach last Index

Previous

In this post, we will see how to find Minimum Number of Jumps to reach last Index.


Problem

Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a jump that can be made from this index. The length of a jump can vary from 1 to A[index].
If value on any index is zero, this means that you can not move forward from this index.
Find the minimum number of jumps required to reach the last index. If the answer is not possible for any case, print “Not Possible”.

Input :
int[] A = { 2, 3, 1, 1, 4 }
Output :
2

Input :
int[] A = { 2, 0, 0, 1, 4 }

Output :
Not Possible


Solution

APPROACH – I :
A basic brute force solution can be achieved by using a recursive approach and making calls to every possible reachable index from the current index.
Now, what does that mean?

  • We are given the array where each index contains the length of the maximum jumps that can be made from that index.
    For eg if A[i] = x, this means that from index ‘i’ we can jump to index  i+0,  i+1,  i+2 … i+x  and obviously only if these indices are in bounds.
  • Here making a call is equivalent to a jump for which we need to keep a jump variable in the function call and increment it in every recursive call made.
  • The base case condition will be, when the current index in the function call is eventually the end index. In the base case we compare the number of jumps made to reach this end index with the global minimum variable update it if the current number of jumps made to reach end index is less than the previously global minimum jump and return from the current call. If the current index becomes greater than the last index, then return from the current call as this is not the result we are looking for.

Steps:

  1. Start from index zero and initialize the number of jumps made variable to 0.
  2. Now for every index that is, in every call, start a loop from 1 to value at current index in the given array indicating the lengths of jump to be made in the next call. Make the function call with current index incremented by the length of jump and number of jumps by 1.
  3. When in base case, that is, when the current index in the call is equal to the last index, compare the number of jumps with the global min jumps variable, update it if the number of jumps made in this call is less than the previously global minimum jump and return from the current call.
    Here we will be using reactive recursive calls, so when the current index in the call is greater than the last index, we simply return from the call without doing any comparisons.

Time Complexity Discussion:
For an array of length n, at every index ‘i’ we are making A[i] jumps which in the worst case can be equal to n. Hence, there can be a total of ‘n’ potential calls from all the ‘n’ indices, therefore the worst time complexity of this solution is O(n^n).

APPROACH 2 :

In the above recursive solution, we can clearly see a lot of redundant calls, therefore for the reduction of the number of calls and eventually for reduced time complexity, we can use Dynamic programming approach.

  • For any index ‘i’ we can actually store the minimum number of jumps required to reach this index and then from here we can calculate the same for all the reachable indices from this index ‘i’ (‘reachable indices’ term is explained in the previous approach).
  • Now for any current index, the minimum number of jumps required to reach any ‘reachable index’ from start(‘0’ th index) is minimum jumps required to reach this current ‘i’th index from start(‘0’ th index) + 1 (to reach index ‘i+x’ directly from index ‘i’) , that is,
    minJumps[i+x] = minJumps[i] + 1
    Where, x can be 1, 2, 3…A[i]
  • Possibly We will be reaching the same index more than once with different number of jumps, but we want the minimum value, therefore, we update any minJumps[i] only if the current number of jumps required to reach ‘i’ is less then the current value at minJumps[i]

Time Complexity Discussion :
Again in this approach, from any index ‘i’ we are calculating minimum number of jumps of all the reachable indices by visiting all the reachable indices from any index, which can be ‘n’ in a worst case, and we are doing this for all n indices.
Therefore, the time complexity of this algorithm is O(n^2).

Before moving on to the next approach, just think if we could do better by using a greedy approach and making greedy coices for next index to jump on, rather than exploring all the possibilities using Dynamic programming.

Approach – III :
Yes we can definitely solve the given problem more efficiently by adopting a greedy approach.

  • The basic strategy would be to keep the track of Maximum reachable index the whole time which will eventually be updated frequently as we move through the given array and as soon as we reach this Maximum reachable index, we increment our number of jumps.
  • For this, we maintain 2 variables which stores the value of current index and Maximum reachable index. The very first thing we do after reaching any index is update the value of Maximum reachable index by comparing it with current Index + A[current Index] (indicating the maximum length of any jump that can be made from here) and we upadate Maximum reachable index value if value of current Index + A[current Index] is greater than Maximum reachable index. That is,

MaxReachable = max( MaxReachable,  current Index + A[current Index])

  • One point to reconsider is, What if after the updation of this Maximum reachable index its value is less than or equal to current Index?
    Well, this the case where we can not move from this current position and hence we can never reach the end index, therefore, in this case we simply return -1, indicating that no answer is possible in this case.

Now, we need to think about the correctness of our greedy approach again.

Can simply incrementing number of jumps when the value of current index is equal to max reachable index, always yield the correct answer everytime?

The answer would be a No, as max reachable index is getting updated and incremented by a value of A[current index] every time, this way value of current index can never be equal to max reachable index except for the case when the answer for a case isn’t possible.

  • For making our approach perfect, we can take another variable which keeps the track of current reachable index, and instead of incrementing the value of jump when current index is equal to Max reachable index, we will increment jump when the current Index becomes equal to current reachable, and at this moment we update the current reachable to max reachable index also.

Time Complexity Discussion :
We visit every index exactly once and keep updating the declared variables as we traverse the given array having ‘n’ elements. Therefore, the worst time complexity of this algorithm is O(n) where n is the size of the given array.

That’s all about the Minimum Number of Jumps to reach last Index.

Previous

Join Our News Letter – Stay Updated

Subscribe to Awesome Java Content.




Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog