Jump Game II Algorithm

You're at the start of an array. Each element tells you the maximum distance you can jump forward from that position. Find the minimum number of jumps to reach the end.

The Problem

Given nums = [2, 3, 1, 1, 4], return 2.

Jump from index 0 to index 1 (value 3), then jump 3 steps to the last index.

You're guaranteed to be able to reach the end.

The Greedy Insight

Think of it like BFS on the array. Each "level" is the set of positions reachable with one more jump. You want to know how many levels it takes to reach the end.

Track three things:

• jumps — the current jump count.
• currentEnd — the farthest index reachable with the current number of jumps.
• farthest — the farthest index reachable with one more jump.

When you pass currentEnd, you must take another jump.

The Code

function jump(nums) {
  let jumps = 0;
  let currentEnd = 0;
  let 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;
}

console.log(jump([2, 3, 1, 1, 4])); // 2
console.log(jump([2, 3, 0, 1, 4])); // 2

Walkthrough

nums = [2, 3, 1, 1, 4]

• i=0: farthest = max(0, 0+2) = 2. i === currentEnd(0), so jump. jumps=1, currentEnd=2.
• i=1: farthest = max(2, 1+3) = 4. Not at currentEnd yet.
• i=2: farthest = max(4, 2+1) = 4. i === currentEnd(2), so jump. jumps=2, currentEnd=4.
• i=3: already past the loop (we stop at nums.length - 1 = 3, but farthest >= last index).

Result: 2 jumps.

Complexity

• Time: O(n) — single pass.
• Space: O(1) — three variables.

The Trade-off

This greedy approach is optimal for the basic problem. But if each jump had different costs (not just counting jumps), you'd need dynamic programming or Dijkstra's algorithm to find the minimum-cost path.