Jump Game

Consider the array 1, 2, 3, 4, 5, 6 We can Jump from index 0 to index 1 Then we jump from index 1 to index 2 Then finally make a jump of 3 to reach index N-1 There is also another path where We can Jump from index 0 to index 1 Then we jump from index 1 to index 3 Then finally make a jump of 2 to reach index N-1 So multiple paths may exist but we need to return the minimum number of jumps in a path to end which here is 3.

Consider the above figure: We are initially at index 0, ARR[0] is 2 which represents we can jump a maximum of 2 steps. We jump 1 index from 0 to 1. At index 1, 'ARR[1]' is 3 which represents we can jump a maximum of 3 steps so we jump 3 indices from 1 to 4 to reach the last index. Hence we return 2. It can be proved that the end can't be reached in less than 2.

Brute Force Approach

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’.

Time Complexity

O(N ^ N), Where ‘N’ denotes the number of elements present in the sequence.

In each recursive call, we can call at the max number of elements equal to the value at a current index which can be at most ‘n’ according to the constraints hence we get a time complexity of the order of N ^ N.

Space Complexity

O(N). Where ‘N’ denotes the number of elements present in the sequence.

As in the case of recursion the space complexity is proportional to the depth of the recursion tree. Which in this case is proportional to the number of elements in the sequence. Therefore overall space complexity is O(N).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of sample input 1 :

Sample Input 2:

Sample Output 2:

Constraints: