Jump Games

Given an array nums where nums[i] is the maximum number of steps you can jump forward from index i, two classic problems ask: can you reach the end, and if so, what is the fewest number of jumps?

Jump Game I — Can You Reach the End?

Keep a running variable farthest that tracks the maximum index reachable so far. If you ever reach an index beyond farthest, you are stuck.

function canJump(nums) {
  let farthest = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;        // stranded
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}

console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false

One pass, O(n) time, O(1) space. The greedy insight: never bother choosing which jump to take — just track the frontier of what is reachable.

Jump Game II — Minimum Jumps

Now you need the fewest jumps to reach the last index. Think of it as implicit BFS: each “level” is the set of indices reachable with exactly k jumps. Expand the frontier greedily.

function minJumps(nums) {
  let jumps = 0;
  let currentEnd = 0;   // end of the current BFS layer
  let farthest = 0;     // farthest reachable from this layer

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {
      // We must take a jump to proceed
      jumps++;
      currentEnd = farthest;
      if (currentEnd >= nums.length - 1) break;
    }
  }

  return jumps;
}

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

Why BFS Layers Prove Optimality

Picture each group of indices reachable in exactly k jumps as a BFS layer. Expanding greedily to the farthest reachable index at each layer boundary is optimal because:

1. Any index in layer k+1 requires at least k+1 jumps — you cannot skip layers.
2. Choosing the farthest expansion maximizes the indices covered in layer k+1, which can only reduce or maintain the number of layers needed.

The argument is an exchange argument in disguise: if you jumped somewhere closer, you could swap that choice for the farther jump without increasing the layer count, but potentially decreasing it.

Up Next

Shift from array problems to tree construction: build an optimal prefix code with Huffman encoding.