Jump Game

Posted: 25 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given an array 'ARR' of ‘N’ integers. You have to find the minimum number of jumps needed to reach the last index of the array i.e ‘N - 1’ if at any index ‘i’ we can jump to an index ‘i + k’ such that 1<= ‘k’ <= ARR[i] i.e the element you are currently at represents the maximum distance you can jump from the current element.

Your goal is to reach the last index in the minimum number of jumps.

Assume that, under the given constraints, you can always reach the last index.

Note:
Consider 0 based indexing.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the given sequence. 

The second line of each test case contains ‘N’ space-separated integers denoting the elements in the sequence.
Output Format:
For each test case, print a single line containing a single integer denoting the minimum number of jumps required to reach the last index.

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 <= 50
1 <= N <= 10 ^ 4
1 <= ARR[i] <= 10 ^ 4

Where ‘ARR[i]’ denotes the ‘i-th’ element of the ‘ARR’.

Time limit: 1 sec.
Approach 1
  • For each index, we find all possible locations we can jump to i.e if we are currently at an index ’i’ and ‘ARR[i]’ = k then we recursively find the answer for all indices from i + 1 to i + k and take the minimum of the answer and add 1 to it to find the minimum number of jumps to reach index last index from index ‘i’.
  • For example, Consider the array : 2, 3, 1, 4
  • We will have the following recursion tree:
  • We can see the arrows in red signify the least number of jumps to reach the last index. In this case, 2 paths are possible each with 2 jumps hence we return 2.

Keeping the above example in mind, we can write the following Recursive solution:

  • If the current index is the last index return 0
  • Let ‘CURRIDX; be the index we are currently at and trying to reach the last index from ‘CURRIDX’ in a minimum number of jumps. And ‘MINJUMP’ be the minimum number of jumps needed.
  • Take a loop from ‘i = 1’ to arr[CURRIDX]’ and find the answer for all possible jumps from the current index
  • Try all possible jumps from the current index(a store that in a variable ‘CURRANS’ and recursively find the minimum of all possible jumps.
  • After each iteration, update the variable ‘MINJUMP’ which stores the minimum number of jumps needed to reach the last index.
  • Finally, return the value of ‘MINJUMP’.

 

Try Problem