4.26.2 — Jump Game

LeetCode 55 · Medium · ★ Blind 75

The problem

nums[i] is the maximum number of steps you can jump forward from index i. Starting at index 0, can you reach the last index?

[2,3,1,1,4]   →  true    (jump 1 to index 1, then 3 to the end)
[3,2,1,0,4]   →  false   (every route lands on the 0 at index 3)

The pattern

The DP version asks, for every index, whether the end is reachable from it — O(n^2), because each index checks every index it can jump to.

The greedy version is one pass, and it comes from a single realisation:

You do not care about the route. You only care how far you can get.

Walk left to right, carrying furthest — the largest index reachable so far. At each position i:

• If i > furthest, you cannot even stand here. Return false.
• Otherwise update furthest = max(furthest, i + nums[i]).

If you get through the loop, the end is reachable.

Why the greedy is correct

Worth proving, because "track the furthest reach" sounds too simple.

Every index up to furthest is reachable. Reachability here is downward closed: if you can jump from i to i + nums[i], you can also stop at any index in between, since nums[i] is a maximum and shorter jumps are allowed.

So there is no need to track which indices are reachable — a single number describes the whole set. That is why one variable suffices and why no path needs remembering.

The word "maximum" in the problem statement is doing the work. If jumps had to be exact, the reachable set would be full of holes and this argument would collapse. That is the assumption to name.

The solution

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        furthest = 0

        for i, n in enumerate(nums):
            if i > furthest:
                return False                  # cannot even reach this index
            furthest = max(furthest, i + n)
            if furthest >= len(nums) - 1:
                return True                   # early exit

        return True

TypeScript

function canJump(nums: number[]): boolean {
  let furthest = 0;

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

  return true;
}

Check i > furthest before updating. You must be able to stand on i before you can jump from it. Updating first would let a stranded index contribute its jump.

The early exit is optional but free, and it makes the common case fast.

furthest starts at 0, because you begin at index 0 with no jumps taken.

Trace

[3,2,1,0,4]

i	reachable?	i + nums[i]	furthest
0	yes (0 ≤ 0)	3	3
1	yes (1 ≤ 3)	3	3
2	yes	3	3
3	yes	3	3
4	no (4 > 3)	—	return false

The 0 at index 3 is the wall. Nothing before it reaches past index 3.

The backwards version

There is an equally clean solution that walks from the right:

goal = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
    if i + nums[i] >= goal:
        goal = i                      # this index can reach the goal, so it becomes the goal
return goal == 0

Read it as "can anything reach the goal? if so, that becomes the new goal", shrinking the target leftwards. If the goal reaches index 0, the start can reach the end.

Same complexity. Some people find it more obviously correct because it never has to argue about reachable sets. Know both and pick the one you can explain fastest.

Complexity

O(n) time, O(1) space — against O(n^2) time and O(n) space for the DP.

Where this goes next

• Jump Game II — the fewest jumps, not just whether it is possible. The greedy becomes a level-by-level sweep. 4.26.3.
• Jump Game III — jumps go both directions, so reachability is no longer downward closed and the greedy collapses. It becomes BFS or DFS on a graph. That contrast is worth holding: the greedy here depends entirely on moving forward only.
• Jump Game IV, VI — BFS and DP with a monotonic deque respectively.
• Video Stitching, Minimum Number of Taps to Water a Garden — interval-covering problems with the same "furthest reach" structure.

What the interviewer will push on

"Why does tracking one number work?" Reachability is downward closed, because nums[i] is a maximum and you may jump less. So the reachable set is always a prefix, and a prefix is described by its end.

"Where does the word maximum matter?" If jumps were exact, the reachable set would have holes and the argument fails.

"Why check i > furthest first?" You must be able to stand somewhere before jumping from it.

"What is the DP solution and why is it worse?" O(n^2) checking every reachable index from every position.

"What if you could jump backwards too?" The greedy breaks; it becomes a graph search.

One thing to volunteer: give the downward-closed argument before writing the loop. Greedy solutions are only convincing with the reason attached, and 4.25 makes that the whole point of the chapter.

Next: 4.26.3 Jump Game II — the same array, now counting jumps, and the greedy turns into a level sweep.