Jump Game II

Find the fewest jumps to reach the end. Think in levels: all indices reachable with k jumps form a window. While scanning the current window, track the farthest you could get with one more jump; when you reach the window's end, take a jump and move to the next window.

Traced input: nums = [2, 3, 1, 1, 4] → 2. Original problem: neetcode.io/problems/jump-game-ii

Complexity

One pass.

Key idea

• end marks the edge of what the current number of jumps can reach.
• far is the farthest reachable with one more jump from anywhere in the window.
• At i == end, you must jump: jumps++, end = far.
• Loop to n − 2: you never jump from the last index.

Common mistakes

• Looping to n − 1 counts an extra jump when end lands exactly on the last index.
• Greedily jumping as far as possible from each position is wrong.

Solution

int jump(int[] nums) {
    int jumps = 0, end = 0, far = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        far = Math.max(far, i + nums[i]);
        if (i == end) {
            jumps++;
            end = far;
        }
    }
    return jumps;
}

def jump(nums: List[int]) -> int:
    jumps = end = far = 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == end:
            jumps += 1
            end = far
    return jumps

int jump(vector<int>& nums) {
    int jumps = 0, end = 0, far = 0;
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        far = max(far, i + nums[i]);
        if (i == end) {
            jumps++;
            end = far;
        }
    }
    return jumps;
}

Edge cases

Each one has its own trace in the interactive view.