Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Jump Game
• Main tags: Array, Dynamic Programming, Greedy

What the problem is really asking

Each position tells how far the player is allowed to jump from that spot.

The goal is not to find the minimum number of jumps. It is only to decide whether the last index is reachable at all.

So the real question is:

While moving from left to right, does there ever come a point that is impossible to reach?

If the scan never gets stuck before the end, the answer is True. If the scan reaches an index that cannot be entered, the answer is False.

The simplest intuition

At index i, two facts matter:

• whether index i itself is reachable
• if it is reachable, how far jumping from there can extend the reachable range

That suggests tracking a running frontier:

• farthest_reachable means the furthest index known to be reachable so far
• when standing at i, if i > farthest_reachable, the path is already broken
• otherwise, update the frontier with max(farthest_reachable, i + nums[i])

This is the core greedy idea.

Why dynamic programming is a useful stepping stone

A natural first thought is dynamic programming:

• mark index 0 as reachable
• from every reachable index, mark the next allowed positions as reachable too

That works, but it does extra work because many positions get revisited conceptually.

The important realization is that the exact set of reachable positions does not matter. Only the furthest reachable boundary matters. Once every index up to some boundary is reachable, keeping the full table is unnecessary.

That observation compresses the DP idea into a greedy scan with O(1) extra space.

Optimal solution

The optimal solution is a single left-to-right pass.

For each index:

1. If the current index is beyond the furthest reachable boundary, return False.
2. Otherwise, extend the boundary using the jump length at this index.
3. If the boundary reaches or passes the last index, return True.

This works because every reachable position before the current boundary has already been accounted for, so there is never a reason to backtrack.

How to derive the greedy rule

A practical derivation looks like this:

1. Start with small examples such as [2, 3, 1, 1, 4] and [3, 2, 1, 0, 4].
2. Notice that after processing the prefix, what matters is the furthest place that prefix can reach.
3. The exact path used to get there does not matter, only the best reach from any reachable index.
4. That means a single running maximum captures all useful information from the prefix.
5. Once an index lies beyond that maximum, no future index can fix the gap, because reaching any future index would already require crossing it.

That last point is why the greedy test is both safe and complete.

Complexity

• Time: O(n)
• Space: O(1)

Python solution

from typing import Sequence


def can_reach_last_index(jump_lengths: Sequence[int]) -> bool:
    """Return True when the last index is reachable from index 0."""
    if not jump_lengths:
        return False

    last_index = len(jump_lengths) - 1
    farthest_reachable_index = 0

    for current_index, maximum_jump_length in enumerate(jump_lengths):
        if current_index > farthest_reachable_index:
            return False

        candidate_reach = current_index + maximum_jump_length
        farthest_reachable_index = max(
            farthest_reachable_index,
            candidate_reach,
        )

        # Once the reachable frontier covers the end, the answer is settled.
        if farthest_reachable_index >= last_index:
            return True

    return True


class Solution:
    def canJump(self, nums: list[int]) -> bool:
        """LeetCode entry point."""
        return can_reach_last_index(nums)

Why this works

The algorithm maintains this invariant:

• before processing index i, every index up to farthest_reachable_index is reachable

Then:

• if i is outside that boundary, index i is unreachable, so the last index is unreachable too
• if i is inside that boundary, the jump from i can only expand the reachable region, never shrink it

By the end of the scan, either the frontier failed before some index or it covered the last index. Those are exactly the two possible outcomes.

Practical takeaway

This is a good example of turning a reachability problem into a prefix invariant.

Instead of asking, “Which exact jumps should be taken?”, the better question is, “How far can the processed prefix reach?”

Once that reframing is clear, the greedy solution becomes short, fast, and easy to defend in an interview.