Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

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

For example:

Given array A = `[2,3,1,1,4]`

The minimum number of jumps to reach the last index is `2`

. (Jump `1`

step from index 0 to 1, then `3`

steps to the last index.)

**Solution**. At first sight, this problem looks like coin change, which has O(n^2) solution. But this exceeds time limit. Then I found this problem can be solved in BFS way. Basically, we can think all elements which we can reach at most 1 step as level 1, all elements which we can reach at most 2 steps as level 2. In level 1, we find the furthest element level 1 can reach, the furthest will be the boundary for level 2.

Below is an example for the jump.

elements in level 1 can mostly jump to position 4. In level 2, it can mostly jump to position 8.

public static int jump(int[] A) { int currLong = 0, nextLong = 0, level = 0; for (int i = 0; i < A.length; i++) { if (i - 1 == currLong) { level++; currLong = nextLong; } nextLong = Math.max(nextLong, A[i] + i); } return level; }

Check my code on github.