Jump Game II

Approach Summary

BFS-like greedy: track current window end and farthest reach. When reaching window end, increment jumps and extend window.

Full Solution & Approach

Minimum jumps is a BFS over reachability: think of the array in "levels", where level k is the set of indices reachable in exactly k jumps. Maintain current_end (the farthest index reachable within the current jump count) and farthest (the farthest index reachable from anywhere inside the current level). Iterate; each time the index reaches current_end, you must spend one more jump, so increment jumps and move current_end to farthest. The answer is the number of times current_end is extended before the end is reached. The greedy is optimal because every index in the current level is exhausted before committing a jump — you can never do better than jumping to the farthest reachable position, since any shorter jump reaches a subset of what the farthest jump reaches.

A single pass with constant work per element — O(n) time. Two scalars — O(1) space.

Solution Code

Solution

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

function jump(nums) {
  let jumps = 0, currentEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

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

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

Edge Cases to Watch

Single element — already at the end, 0 jumps
Two elements — one jump
A jump that overshoots the end — the last index is still reachable
Zeros — unreachable positions are never entered because jumps are planned from reachable ranges

How to Recognize This Pattern

Minimum jumps to reach end
BFS-like greedy

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)