Jump Game Solution

Problem

Given an array of non-negative integers where each element represents the maximum number of steps you can jump forward from that position, determine whether you can reach the last index starting from index 0.

Input: nums = [2, 3, 1, 1, 4]
Output: true
Explanation: Jump 1 step to index 1, then 3 steps to reach the last index.

A case that returns false:

Input: nums = [3, 0, 0, 0, 4]
Output: false
Explanation: From index 0 you can reach indices 1, 2, or 3 — all have value 0 and cannot carry you to index 4.

Intuition

The question is really asking whether the reachable frontier starting at index 0 can stretch far enough to cover the last index. At every position, the frontier extends by that position's jump value, but if you step beyond the frontier you are stranded. The key insight is that you only need to track the farthest position reachable so far — not every possible path — because any index inside the frontier is automatically reachable too.

Approach 1 — Reachability Array (DP)

Track a boolean array marking which positions are reachable. For every reachable position, mark all positions it can jump to as also reachable.

Steps:

Create a reachable array of length n, set reachable[0] = True.
Iterate i from 0 to n-1; skip any position that is not marked reachable.
For each reachable position, mark all positions from i+1 to min(i + nums[i], n-1) as reachable.
Return reachable[n-1].

1def canJump(nums: list[int]) -> bool:
2    n = len(nums)
3    reachable = [False] * n
4    reachable[0] = True
5    for i in range(n):
6        if not reachable[i]:
7            continue
8        # mark every landing spot within reach of position i
9        for jump in range(1, nums[i] + 1):
10            if i + jump >= n:
11                break
12            reachable[i + jump] = True
13    return reachable[-1]

Time: O(n²) — in the worst case each of the n reachable positions updates up to n neighbors
Space: O(n) — the boolean reachability array

Approach 2 — Greedy (Max Reach)

Instead of a full boolean array, track only the farthest index reachable so far. The moment the current index exceeds that frontier, return false immediately.

Steps:

Initialize max_reach = 0.
Iterate i from 0 to n-1.
If i > max_reach, return False — the current position is beyond our frontier.
Update max_reach = max(max_reach, i + nums[i]).
Return True after the loop completes without triggering the early exit.

1def canJump(nums: list[int]) -> bool:
2    max_reach = 0
3    for i, jump_length in enumerate(nums):
4        if i > max_reach:
5            # stranded beyond the farthest reachable position
6            return False
7        max_reach = max(max_reach, i + jump_length)
8    return True

Time: O(n) — single pass through the array
Space: O(1) — only the max_reach integer

Complexity Summary

Approach	Time	Space	When to use
Reachability Array	O(n²)	O(n)	When you need to know which specific positions are reachable, not just the endpoint
Greedy (Max Reach)	O(n)	O(1)	Standard solution — always prefer this

Common Mistakes

Treating nums[i] as an exact distance, not a maximum: You can jump any number of steps from 0 to nums[i]. In [2, 3, 1, 1, 4], jumping 1 step from index 0 to index 1 is perfectly valid.
Using i >= max_reach instead of i > max_reach: The position exactly at max_reach is still reachable — only positions strictly past it are not. Using >= incorrectly returns false at i = 0 since 0 >= 0 is immediately true, breaking every input.
Thinking zeros create impassable walls: In [3, 0, 2, 0, 4] the path 0 → 2 → 4 skips the zero at index 1 entirely. The frontier approach naturally handles this without any special zero-checking.
Adding a redundant final check return max_reach >= n - 1: If the loop finishes without the early return, every index up to n-1 was already within the frontier, so return True alone is correct and the extra check is noise.
Using backtracking or DFS without memoization: Naively exploring all jump paths leads to O(2^n) calls. The greedy insight collapses this to a single scan — only the farthest reach ever matters.

Jump Game — Solution