Minimum Number of Jumps to reach last Index

Table of Contents

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

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.

Related Posts

  • Maximum number of vowels in a Substring of given length
    18 June

    Maximum Number of Vowels in a Substring of Given Length

    Table of ContentsApproach – 1 Generate All Substrings Using substring() MethodApproach – 2 Using Sliding Window Method (Linear Time Solution) In this article, we will look at an interesting problem related to the Strings and [Sliding-Window Algorithm](https://java2blog.com/sliding-window-maximum-java/ “Sliding-Window Algorithm”). The problem is : "Given a String we have to Find the Maximum Number of Vowel […]

  • Find first and last position of element in sorted array
    04 June

    Search for a range Leetcode – Find first and last position of element in sorted array

    Table of ContentsApproach 1 (Using Linear Search)Approach 2 (Using Modified Binary Search-Optimal) In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is […]

  • 30 April

    Convert Postfix to Infix in Java

    Learn about how to convert Postfix to Infix in java.

  • Prefix to postfix in java
    30 April

    Convert Prefix to Postfix in Java

    Learn about how to convert Prefix to Postfix in java.

  • Data structures in java
    16 April

    Data Structures in java

    Table of ContentsArray Declare and initialize array in javaAdvantages of arrayDisadvantages of array ExampleArray practice programsStackStack implementation using ArrayStack implementation using LinkedListImplementationPractice ProgramsQueueQueue implementation using arrayQueue implementation using LinkedListImplementationLinkedListImplementationLinkedList Practice ProgramsBinary treeImplementationBinary tree practice programsBinary Search treeImplementationBinary search tree Practice programsTrieImplementationHeapImplementationGraphImplementation Inbuild data structures in javaStringHashMapLinkedHashMapArrayListLinkedListHashSet In this post, we will see about various data […]

  • 29 November

    Top 100+ Java coding interview questions

    Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.