LeetCode 45 · Medium · Greedy

Jump Game II

From index i you may jump forward up to nums[i] steps, and the last index is always reachable. Return the fewest jumps that take you from index 0 to the last index.

O(n)time
O(1)space
BFS levelsas windows

comma-separated integers · 1–12 values · each 0 to 9 · the last index must be reachable

public int jump(int[] nums) { int res = 0; int l = 0, r = 0; // window: indices reachable in res jumps while (r < nums.length - 1) { int farthest = 0; for (int i = l; i <= r; i++) { farthest = Math.max(farthest, i + nums[i]); } l = r + 1; r = farthest; res++; } return res;}
res
0
[l, r]
—
i
—
i + nums[i]
—
farthest
—

Why it works

  1. Brute force is a DP: jumps[j] = 1 + min(jumps[i]) over every i that reaches j. That is O(n²), or a BFS over an explicit graph with O(n²) edges.
  2. The BFS levels are contiguous windows. If index j is reachable within res jumps, so is every index before it. So level res is a window [l, r], and the next level runs from r + 1 to the farthest jump out of the window.
  3. Each index is scanned once, inside exactly one window: O(n) time, and only l, r, farthest and res: O(1) space.
  4. Pitfall: loop while r < nums.length - 1. Jumping once more after the window already covers the last index overcounts, and [0] needs 0 jumps.
  5. Related: Jump Game (55) only asks whether the end is reachable. If farthest ever fails to pass r, the window is stuck and the end is unreachable.