A last-mile van still starts at depot 0. From stop i the remaining charge still skips at most nums[i] stops forward. Dispatch already knows the last drop is reachable — that was Jump Game. This week they bill the driver per hop. The intern reused the boolean farthest loop and reported 1 whenever the end sat inside the reach. A three-stop stub looked fine. A chain of 1-charge stops is n - 1 hops, and that boolean loop never counted a layer.

Jump Game II asks for the fewest jumps that still reach the last index. An array already gives nums[i] for free. The last index is always reachable. Searching every hop tree uses that and still pays an exponential min. You are not asked whether you can arrive.

This is an interview writeup, not a second reachability lecture. The Jump Game writeup owns the boolean farthest. Here we only count layers.

The problem

Given an int[] nums of non-negative jump lengths, you start at index 0. From index i you may land on any in-bounds index in i .. i + nums[i]. Return the minimum number of jumps to reach the last index. Some sequence always exists.

[2, 1, 3, 1]     →  2     0 → 2 → 3
[1, 1, 1, 1]     →  3     each hop covers only the next cell
[4, 0, 0, 0]     →  1     one hop from 0 covers the end
[0]              →  0     already on the last index

Note: nums[i] is a maximum, not a required step. Jump Game was a boolean: can any path arrive? This prompt counts layers. Do not reuse the reachability loop as if farthest >= n - 1 were a jump count.

Every jump tree is the honest brute force

From index i, recurse on every legal landing and take 1 + min. If you already sit on the last index, 0. Correct. Exponential in the branching of fat windows.

int jumpDfs(int[] nums) {
    return minFrom(nums, 0);
}

int minFrom(int[] nums, int i) {
    if (i >= nums.length - 1) {
        return 0;
    }
    int best = nums.length;
    int cap = Math.min(nums[i], nums.length - 1 - i);
    for (int step = 1; step <= cap; step++) {
        best = Math.min(best, 1 + minFrom(nums, i + step));
    }
    return best;
}

A queue BFS that enqueues every landing is the same search in layers, billed per edge. Memoizing “min jumps from i” makes the tree a DAG and O(n²) — still more than you need. At n in the hundreds you paid a jump tree for a question one layer wall answers: when does this layer buy the next hop?

One pass: BFS layers on the array

Walk left to right, but stop before the last index — you never jump from the destination. Keep three integers: farthest (rightmost landing any index in the current layer can launch to), end (the right wall of this jump), jumps.

  • Fold i + nums[i] into farthest.
  • When i hits end, the current layer is exhausted: jumps++, and the next wall is that farthest.

You never fork a path. You never enqueue indexes. The array is the queue: the next layer is (end, farthest].

[2, 1, 3, 1]     jumps=0  end=0  farthest=0

i=0  farthest=max(0, 0+2)=2   i==end  jumps=1  end=2
i=1  farthest=max(2, 1+1)=2
i=2  farthest=max(2, 2+3)=5   i==end  jumps=2  end=5
     i stops before last index

min jumps = 2

The Java is that walk:

int jump(int[] nums) {
    int jumps = 0;
    int end = 0;
    int farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == end) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
}

Time is O(n) — one pass, constant work per index. Extra space is O(1) — three running integers. The DFS is correct and the wrong bill once n leaves the toy range.

Note: Do not iterate through the last index. If end already sits on n - 1, one more i == end would increment a hop you never take. The prompt promised reachability; if a 0 can trap you, that is Jump Game, not this loop.

What interviewers usually poke next

  • Jump Game (boolean). Reachability, not a count. The writeup owns the running farthest. Do not mix the loops.
  • Reconstruct hops. Store, per layer, one index that achieved farthest. The count loop does not keep a path.
  • Not always reachable. Then you must detect i == end while farthest == end and you are short of the last index. This prompt does not ask that. Say so.
  • Single element, or one hop that covers the end. 0 jumps and 1 jump. The i < n - 1 bound handles both: the loop never runs, or it fires once at i = 0.

You are done with this problem when you can walk [2, 1, 3, 1] and [1, 1, 1, 1] on a whiteboard as layers, and you can say out loud why the jump tree is correct, why you do not need it, and why Jump Game’s boolean farthest is a different question.