Jump Game II

Examples

Input: nums = [2, 3, 1, 1, 4]
Output: 2

Jump 1 step from index 0 to index 1, then 3 steps to the last index - 2 jumps total.

Input: nums = [2, 3, 0, 1, 4]
Output: 2

Jump from index 0 to index 1, then from index 1 to index 4.

Input: nums = [1, 1, 1, 1]
Output: 3

Each jump can only move 1 step, so it takes 3 jumps to cross 3 gaps.

Constraints

• 1 <= nums.length <= 10^4

• 0 <= nums[i] <= 1000

• You're guaranteed you can always reach the last index.

Approach

You could search every combination of jumps and take the shortest path, but that revisits the same positions over and over. Instead, think in terms of levels, like a breadth-first search: level 0 is just index 0; level 1 is every index reachable in one jump from level 0; level 2 is every index reachable in one more jump from anywhere in level 1; and so on.

Greedily scan through the current level's range, and while doing so, track the furthest index reachable from any position in it. When you reach the end of the current level's range, you're forced to take another jump - so increment the jump count and the level's range becomes "up to that furthest index".

Solutions

Brute Force - Try Every Jump (Recursion)

From each index, recursively try every possible jump length and take the path that reaches the end in the fewest jumps.

function jump(nums) {
  function minJumpsFrom(pos) {
    if (pos >= nums.length - 1) return 0;
    let best = Infinity;
    const maxJump = Math.min(nums[pos], nums.length - 1 - pos);
    for (let step = 1; step <= maxJump; step++) {
      const rest = minJumpsFrom(pos + step);
      if (rest !== Infinity) best = Math.min(best, 1 + rest);
    }
    return best;
  }
  return minJumpsFrom(0);
}

Time: O(2^n) in the worst case, since each position branches into many jump choices · Space: O(n) recursion depth

Optimal - Greedy Level-by-Level (BFS-style)

Scan through the current jump's reachable range, tracking the furthest index the next jump could reach. When the scan hits the end of the current range, commit to another jump.

function jump(nums) {
  let jumps = 0;
  let currentEnd = 0;
  let furthest = 0;

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

Time: O(n) · Space: O(1)