Jump Game

The wrong mental model is a tree of jump paths. The useful model is a moving boundary: the farthest index reachable by any valid path found so far.

The greedy solution

Maintain one value:

farthest = the rightmost index reachable from index 0

Scan the array from left to right.

For each index i:

1. If i > farthest, the scan has entered a dead zone. Return False.
2. Otherwise, i is reachable, so its jump capacity may extend the boundary:

   farthest = max(farthest, i + nums[i])
   

3. If farthest reaches the last index, return True.

The complete Jump Game solution is:

def can_jump(nums: list[int]) -> bool:
    farthest = 0
    last = len(nums) - 1

    for i, jump_length in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump_length)

        if farthest >= last:
            return True

    return True

The important detail is the order of the first two operations. An unreachable index must not use its value to extend the boundary.

Why path search is the wrong state

A direct recursive solution follows the wording of the problem:

def can_reach(i: int, nums: list[int]) -> bool:
    if i == len(nums) - 1:
        return True

    for step in range(1, nums[i] + 1):
        if i + step < len(nums) and can_reach(i + step, nums):
            return True

    return False

But different paths can arrive at the same index, causing the same suffix of the array to be explored repeatedly. With enough branching, this becomes expensive quickly. Memoization removes repeated suffix searches, but it still stores more information than the boolean question requires.

The problem does not ask:

• Which path reaches the end?
• How many jumps are required?
• What was the exact history of each path?

It asks only whether the final index is reachable. That lets us compress the state.

There are two obligations:

1. Know whether the current index is reachable.
2. If it is, use its jump range to extend future reachability.

The frontier handles both. We do not choose one physical route. We preserve the widest consequence of all routes considered so far.

The greedy scan does not choose one jump at each step. It summarizes every useful route with one rightmost boundary.

Derive the reachable-prefix invariant

The key invariant is stronger than “farthest is some maximum index”:

Before processing index i, every index in the interval [0, farthest] is reachable from index 0.

This says the reachable region has no holes. Once this is established, the test i > farthest has a precise meaning:

• i <= farthest: index i is reachable and can contribute.
• i > farthest: index i lies beyond the entire reachable prefix and cannot contribute.

Why the reachable region has no holes

Initially, only index 0 is known to be reachable, so the reachable region is [0, 0].

Now suppose every index through farthest is reachable. Take any reachable index j in that prefix. From j, the maximum destination is:

j + nums[j]

Because the jump length is a maximum, the position can land at any valid index between j and j + nums[j]. Therefore, index j contributes an interval of reachable destinations:

[j, j + nums[j]]

These intervals begin at positions already covered by the reachable prefix. Their union extends that prefix to the largest endpoint found:

farthest = max(farthest, j + nums[j])

So the next reachable region is still one contiguous prefix, [0, farthest]. There is no hidden unreachable hole below the boundary.

That interval property is the proof bridge. A maximum endpoint by itself would not be enough; the forward, “up to this many positions” jump rule is what makes the entire region beneath that endpoint reachable.

Why earlier reach dominates narrower reach

Suppose one reachable path reaches index 8 and another reaches index 5. The path reaching 8 is at least as useful for future reachability:

• It can access every position the path reaching 5 could access.
• It may also access positions from 6 through 8.
• The exact route history no longer affects what can be explored from the current boundary.

This is the greedy compression. We retain the farthest consequence, not the history that produced it.

However, do not confuse farthest with one selected route. A frontier is a summary of many possible routes. It is not a claim that the algorithm has physically jumped to that index.

Dry-run: a successful array

Consider:

nums = [2, 3, 1, 1, 4]

The last index is 4.

Index i	nums[i]	Prior farthest	Updated farthest	Meaning
0	2	0	2	The start reaches through index 2
1	3	2	4	Index 1 reaches the target
2	1	4	4	Already inside the reachable prefix
3	1	4	4	Already inside the reachable prefix
4	4	4	8	The target was already reachable

At index 1, farthest becomes 4, so the function can return True immediately.

One valid route is:

0 -> 1 -> 4

But the algorithm does not need to reconstruct that route. It only needs to know that the reachable prefix now includes the target.

Dry-run: a dead zone

Now consider:

nums = [3, 2, 1, 0, 4]

Index i	nums[i]	Prior farthest	Updated farthest	Meaning
0	3	0	3	The start reaches through index 3
1	2	3	3	No extension
2	1	3	3	No extension
3	0	3	3	The frontier stops here
4	4	3	—	Unreachable; return False

Index 3 is reachable, but its maximum jump length is zero. The reachable prefix remains [0, 3].

When the scan reaches index 4, it has crossed the boundary:

4 > 3

No later value can repair that failure. To use nums[4], some valid path would first need to reach index 4. Since every jump moves forward, an unreachable index cannot be used to jump itself—or anything else—back into reachability.

A dead zone is permanent when movement is forward-only.

Translate the invariant into code

The implementation has three meaningful pieces:

def can_jump(nums: list[int]) -> bool:
    farthest = 0
    last = len(nums) - 1

    for i, jump_length in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump_length)

        if farthest >= last:
            return True

    return True

Each variable has one job:

• i identifies the position being examined.
• jump_length is the maximum distance available from i.
• farthest is the right boundary of the reachable prefix.
• last is the target index.

The branch order is part of the correctness argument:

if i > farthest:
    return False

must come before:

farthest = max(farthest, i + jump_length)

Consider the unreachable index 4 in [3, 2, 1, 0, 4]. Its value is 4, but that value is unusable. If the code updated the frontier before checking reachability, it would let an impossible position manufacture new reachability.

That is a common implementation bug: the code may look like a greedy scan while silently violating its own invariant.

The early success check is safe as well:

if farthest >= last:
    return True

The boundary does not need to land exactly on the final index. Reaching beyond it is sufficient because the question asks whether the last index is reachable, not whether every jump must stop at an exact endpoint.

Correctness proof

Initialization

Before the loop, farthest = 0. Index 0 is the starting position, so the reachable prefix is [0, 0]. The invariant holds.

Preservation

Assume the invariant holds before processing index i.

• If i > farthest, index i lies beyond the reachable prefix. No valid path reaches it, so returning False is correct.
• If i <= farthest, the reachable-prefix invariant guarantees that index i is reachable. Its jump capacity extends the reachable region to at most i + nums[i]. Taking the maximum preserves the rightmost endpoint contributed by every reachable index examined so far.

Because each reachable position contributes an interval and those intervals extend from an already reachable prefix, the updated reachable set remains contiguous.

Success

If:

farthest >= last

then some valid path reaches or passes the final index. Returning True is correct.

Failure

If the loop encounters:

i > farthest

then the scan has crossed the entire reachable prefix. Every later index is even farther away, and forward-only jumps cannot cross backward over the gap. Returning False is correct.

Complexity and edge cases

The loop examines each position at most once. Every iteration performs constant-time arithmetic and comparisons.

• Time: O(n)
• Extra space: O(1)

The input array is not counted as auxiliary space.

Important boundary cases:

Input	Result	Reason
nums = [0]	True	The starting index is already the target
nums = [0, 1]	False	Index 1 is unreachable
nums = [2, 0, 0]	True	The first index reaches the target
nums = [1, 0, 0]	False	The reachable prefix stops before the target
A zero after the target is reachable	True	The scan can stop as soon as the target enters the frontier
A jump exceeds the remaining array length	True	Reaching or passing the target is enough

Two interpretation errors cause many failed implementations:

1. Treating nums[i] as an exact jump. It is a maximum. A position may use a shorter jump.
2. Using an unreachable index. Its value is irrelevant because no valid path can stand there.

This problem is also different from related variants. Minimum jumps requires state about jump layers or boundaries. Path reconstruction requires predecessor information. Boolean reachability needs only the reachable-prefix boundary.

The transferable recognition rule

When you see an array problem with:

• ordered positions,
• forward-only movement,
• a maximum reach from each position,
• and a yes/no question about reaching a target,

look for a monotone frontier.

Ask:

1. Does every reachable position contribute an interval of future positions?
2. Does the union of those intervals remain a contiguous prefix?
3. Is failure permanent once the scan moves beyond that prefix?

If the answers are yes, track the farthest reachable index instead of enumerating paths.

In an interview, make the reasoning visible before writing code:

1. Define what farthest means.
2. State the reachable-prefix invariant.
3. Explain why a reachable position contributes an interval.
4. Dry-run one success and one dead zone.
5. Check reachability before using the current jump value.
6. State O(n) time and O(1) extra space.

A greedy solution earns its compression. Here, the compression is valid because the reachable set has no holes, farther reach dominates narrower reach, and crossing the frontier cannot be repaired from behind.