A last-mile van starts at depot 0. From stop i the remaining charge can skip at most nums[i] stops forward — any landing in that window, not a forced exact hop. Dispatch only asks: can this route even reach the last drop, or does a zero-charge stop trap the van short of the door? The intern recursed every legal hop from 0. A five-stop stub returned. A hundred stops with fat windows was still expanding jump trees when the window closed.

Jump Game asks whether some jumps still reach the last index. An array already gives nums[i] for free. Searching every path uses that and still pays an exponential tree. You are not asked for the hops themselves.

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 whether some sequence of jumps reaches the last index.

[2, 3, 0, 1]  →  true     0 → 1 → 3  (index 2 is a dead 0; 1 already covers the end)
[1, 0, 2]     →  false    from 0 you reach 1; nums[1] is 0; index 2 sits outside
[0]           →  true     already on the last index
[4, 0, 0, 0]  →  true     one hop from 0 covers the end

Note: nums[i] is a maximum, not a required step. From a 3 you may jump 1, 2, or 3 (in bounds). Jump Game II asks for the fewest jumps to the last index. That is a different problem. Do not switch prompts.

Every jump tree is the honest brute force

From index i, recurse on every legal landing i + 1 .. i + nums[i]. If any path hits the last index, yes. Correct. Exponential in the branching of fat windows.

boolean canJumpDfs(int[] nums) {
    return jumpFrom(nums, 0);
}

boolean jumpFrom(int[] nums, int i) {
    if (i >= nums.length - 1) {
        return true;
    }
    int cap = Math.min(nums[i], nums.length - 1 - i);
    for (int step = cap; step >= 1; step--) {
        if (jumpFrom(nums, i + step)) {
            return true;
        }
    }
    return false;
}

A BFS from 0 with a queue of indexes is the same search in layers. At n = 8 this is a rounding error. At n in the hundreds you paid a jump tree for a question one running farthest answers: can I still stand here, and how far can the prefix launch me? Memoizing “can i reach the end?” makes the tree a DAG and O(n²) — still more than you need for a yes/no.

One pass: farthest landing so far

Walk left to right. farthest is the rightmost index any position you could already stand on can launch to.

  • If i > farthest, you cannot stand at i. The last index is unreachable.
  • Otherwise fold i + nums[i] into farthest.
  • If farthest already covers the last index, return true.

You never fork a path. A 0 in the middle is fine if some earlier index already jumps over it. A 0 you must stand on, with nothing past it in farthest, is the trap.

[1, 0, 2]     farthest starts 0
i=0  0<=0   farthest=max(0, 0+1)=1
i=1  1<=1   farthest=max(1, 1+0)=1
i=2  2>1    cannot stand here → false

[2, 3, 0, 1]
i=0  farthest=2
i=1  1<=2   farthest=max(2, 1+3)=4  covers last → true

Working backwards is the same fact from the other end: need starts at the last index; a left index that can reach need becomes the new need; you succeed when need falls to 0. Same linear pass. The Java below is the forward farthest:

boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) {
            return false;
        }
        farthest = Math.max(farthest, i + nums[i]);
        if (farthest >= nums.length - 1) {
            return true;
        }
    }
    return true;
}

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

Note: You do not need a path. Reconstructing hops is a different ask. The early farthest >= n - 1 return is optional; scanning the rest still works, but standing past farthest is the failure you must not skip.

What interviewers usually poke next

  • Jump Game II. Fewest jumps to the last index, not a boolean. Name it and stop unless they switch the prompt. Do not reuse this farthest loop as if it counted jumps.
  • Memo DFS. can[i] from the end, or “visited” so you do not re-expand an index. O(n²) time, O(n) extra. Say it is the search with overlapping subproblems removed, then go back to the linear scan.
  • A 0 in the middle. Harmless if an earlier index jumps over it. Fatal if it is the only cell you can stand on and it cannot move.
  • Single element, or nums[0] == 0 with n > 1. Already there is true. Stuck at the start is false. The loop handles both.

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