Jump Game

PROBLEM STATEMENT

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

Approach 2

From the recursion tree in the previous approach, we can easily see that the problems have the property of overlapping subproblems hence we can use the idea of Dynamic Programming to store the results of previous subproblems to reduce our time complexity.
For memoization, we create an array ‘DP’ where DP[i] stores the minimum number of jumps required to reach the last index from the ‘i-th index’ where 0 <= ‘i’< n.

Keeping in mind the above idea, we can use the following approach:

Make a recursive function which takes in 3 parameters current index, given sequence and an array ‘DP’.
If the current index is equal to the size of array -1 (-1 for 0 based indexing.) we return 0 as we don’t need to jump at all as we are already at the destination index.
Otherwise, we will try all possible jumps, i.e from a jump of 1 index to the jump of the maximum possible index and recursively calculate all the values.
Finally, we calculate the minimum of all the values and store it in our ‘DP’ array.

Try Problem

Approach 3

Since we are interested in only the minimum amount of jumps we can come up with a greedy solution.
As an example consider the sequence 5,9,3,2,1,0,2,3,3,1,0

Now, think about the following,

To reach the last index we try to reach the minimum index from which we can reach the last index.

-- Now what is the minimum index from which we can reach the last index in one jump?

From -- index 0 we can at max go 0 + 5 = 5, not 11

From -- index 1, we can at max go 1 + 9 = 10, not 11

From -- index 2, we can at max go 2 + 3 = 5, not 11

From -- index 3,we can at max go 3 + 2 = 5,not 11

From -- index 4 we can at max go, 4 + 1 = 5, not 11

From -- index 5, we can at max go 5 + 0 = 5, not 11

From -- index 6, we can at max go 6 + 2 = 8, not 11

From -- index 7, we can at max go 7 + 3 = 10, not 11

From -- index 8, we can at max go 8 + 3 = 11, yes!

Thus we have to first reach index 8.

-- Now what is the minimum index from which we can reach index 8 in one jump?

-- index 0,we can at max go 0 + 5 = 5, no

-- index 1, we can at max go 1 + 9 = 10, yes

Thus we have to first reach index 1.

-- Now what is the minimum index from which we can reach index 1 in one jump?

-- index 0,we can at max go 0 + 5 = 5, yes

Therefore, 3 jumps in total.

Keeping in mind the above example, we can use the following approach:

Take the variables 'MINJUMP' to store the minimum number of jumps,’curEnd’ to store the farthest index we can go from the current index and 'CURFARTHEST' to store the farthest we can go with the help of elements we have encountered till now.
We initialise the value of 'CUREND' and 'CURFARTHEST' to be 0.
Let's say the range of the current jump is ['CURBEGIN', 'CUREND'].
'CURFARTHEST' is the farthest point that all points in ['CURBEGIN', 'CUREND'] can reach.
Once the current index ‘i’ reaches the 'CUREND' we have reached the maximum possible index we could have reached in 1 jump, therefore, we trigger another jump.
We then set the new 'CUREND' with 'CURFARTHEST', until 'CURFARTHEST' is equal to the last index of the given sequence.

Try Problem