42. Jump Game II

Think of the array as levels of a BFS: from the current jump's reachable range, look ahead to the farthest index any of those positions can reach. When you finish the current range, you must spend one jump to advance to that new farthest range.

Idea

Each jump defines a range of reachable indices. Within the current range, we don't care which index we jump from — only how far the whole range can collectively reach. That farthest reach becomes the next range, costing exactly one jump. This is BFS on the array, counting levels.

Algorithm

1. jumps = 0, cur_end = 0 (end of the current jump's range), farthest = 0.
2. For i from 0 to n - 2:
   • farthest = max(farthest, i + nums[i]).
   • If i == cur_end, we've exhausted the current range → jumps += 1, cur_end = farthest.
3. Return jumps.

Worked example: [2,3,1,1,4]

• i=0: farthest=2. i==cur_end(0) → jump 1, cur_end=2.
• i=1: farthest=max(2,4)=4. i=2: farthest still 4; i==cur_end(2) → jump 2, cur_end=4.
• Loop ends; reached the last index.

Minimum jumps = 2 (index 0 → 1 → 4).

Complexity

• Time: O(n).
• Space: O(1).

class Solution {
    public int jump(int[] nums) {
        int jumps = 0, curEnd = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = farthest;
            }
        }
        return jumps;
    }
}