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.
Sample Input:
5
2 3 1 1 4Sample Output:
2Explanation of given Test Case :
Consider the above figure: We are initially at index 0, ARR[0] is 2 which represents we can jump a maximum of 2 steps. As we can clearly see that to reach the last index in the minimum number of moves, we need to jump 1 index from 0 to 1. At index 1 ARR[1] is 3 which represents we can jump a maximum of 3 steps. Jumping 3 indices from 1 to 4 to reach the last index. Hence the required number of jumps is 2, therefore, we return 2.
If we jump from index 0 to index 2 of two steps we reach at index 2. Further on ARR[2] is 1 so we can jump one step and reach index 3.ARR[3] is 1 so we jump 1 step and reach index 4 which is the last index. In this process, we required a total of 3 jumps which is not the minimum.
Approach :
Greedy Approach
- 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.
Time complexity: O(N)
Space complexity: O(1)
