Fewest Jumps to the End
You get an array a of non-negative integers. You start at index 0.
When you stand on index i, one jump can take you forward to any index from i + 1 up to i + a[i]. You may jump shorter than a[i]. If a[i] is 0, you cannot move from index i.
Return the fewest jumps needed to reach the last index. If the last index cannot be reached, return -1.
Note
If the array has only one element, you are already on the last index, so the answer is 0.
Hint
Think in rounds. After k jumps you can stand on any index inside one block that starts at index 0. The next block ends at the farthest index that any index in the current block can reach. If that farthest index does not move forward, you are stuck.
Examples
Example 1
- Input:
- [2,1,3,1,1,2,1]
- Output:
- 3
Jump from index 0 to index 2, then from index 2 to index 5, then from index 5 to index 6. After one jump you are on index 1 or 2, and neither can reach index 6, so two jumps are not enough.
Example 2
- Input:
- [2,1,0,3]
- Output:
- -1
From index 0 you reach index 1 or index 2. Both of them can only reach index 2, where the value is 0. Index 3 is never reached.
Example 3
- Input:
- [5]
- Output:
- 0
There is one element, so you start on the last index.
Constraints
1 <= a.length <= 400 <= a[i] <= 10
Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.