Frontend Beauty
ESC

Type to search the knowledge base.

Jump Game II

Minimum jumps to last index — BFS layers on the array, greedy end/far windows, O(n) without real queue.

intermediate3 min read
  • dsa
  • greedy
  • interview
  • Google
  • Meta

The problem

Same jump rules as Jump Game I, but return the minimum number of jumps to reach the last index. You may assume it’s always reachable.

[2,3,1,1,4] → 2  // 0→1→4
[2,3,0,1,4] → 2

Brute DP

function jumpDp(nums: number[]): number {
  const n = nums.length;
  const dp = new Array<number>(n).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 1; j <= nums[i] && i + j < n; j++) {
      dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
    }
  }
  return dp[n - 1];
}
Time O(n²)
Space O(n)

Optimal: greedy BFS layers

Think of indices reachable in exactly jumps steps as a BFS level. Track:

  • end — end of current jump range
  • far — farthest index reachable in the next jump
  • When i hits end, take a jump, set end = far
function jump(nums: number[]): number {
  let jumps = 0;
  let end = 0;
  let far = 0;

  // don't need to process last index as a jump start
  for (let i = 0; i < nums.length - 1; i++) {
    far = Math.max(far, i + nums[i]);
    if (i === end) {
      jumps++;
      end = far;
    }
  }
  return jumps;
}
Time O(n)
Space O(1)

Walk [2,3,1,1,4]

i far end jumps
0 2 hit end → jumps=1, end=2 1
1 max(2,4)=4 1
2 4 hit end → jumps=2, end=4 2
stop before last 2

Edge cases

  • n=1 → 0 jumps
  • Always reachable (problem promise)
  • Large jumps that skip far past end

Common mistakes

  • Counting a jump at the last index
  • Returning Jump Game I boolean logic
  • O(n²) only and missing greedy

Interview delivery

  1. Min jumps, reachable guaranteed.
  2. DP baseline.
  3. Level-by-level farthest.
  4. Trace sample.
  5. O(n).

Mental model

BFS on the implicit jump graph, but compressed into windows: the current level is (prev_end, end], and while scanning it you compute the next level’s end as max reach. Each time you finish a level, jumps++.

Why exclude last index in the loop

You don’t take a jump from the last index. Looping to n-2 avoids an off-by-one extra jump when end lands on the last index.

Out-loud answer

“Min jumps, always reachable. Greedy windows: far and end. When i hits end, jumps++, end=far. O(n). DP is O(n²) baseline.”

Further reading