Jump Game

Problem

You are given an integer array nums. You start at index 0. Each nums[i] is the maximum jump length from index i — from i you may step to any index in i+1, i+2, ..., i+nums[i] (as long as it stays in bounds). Return True if you can reach the last index, False otherwise.

Examples

• nums = [2,3,1,1,4] → True — jump 0→1 (length 1), then 1→4 (length 3), landing on the last index.
• nums = [3,2,1,0,4] → False — every route stalls at index 3, whose value 0 allows no further jump; index 4 is unreachable.
• nums = [0] → True — you are already on the last (and only) index.

Constraints

• 1 <= len(nums) <= 10^4
• 0 <= nums[i] <= 10^5

An O(n) scan is expected. The 0 values are what make the problem non-trivial, since a 0 blocks any further jump from that index.

Think about it first

TL;DR

Sweep left to right tracking the farthest reachable index; if a position ever lies beyond the frontier you are stuck — O(n) time, O(1) space.

Approach 1 — Dynamic programming: reachability of every index

Let reach[i] be True if index i is reachable. reach[0] = True; index i is reachable if some earlier reachable j can jump to it (j + nums[j] >= i).

from typing import List

def canJump(nums: List[int]) -> bool:
    n = len(nums)
    reach = [False] * n
    reach[0] = True
    for i in range(1, n):
        for j in range(i):
            if reach[j] and j + nums[j] >= i:
                reach[i] = True
                break
    return reach[n - 1]

Complexity: O(n^2) time, O(n) space. Correct, but the nested scan is wasteful — reachability is monotone, which the greedy exploits.

Approach 2 — Forward greedy: track the farthest frontier

The greedy-choice property (why one frontier number is enough): The set of reachable indices is a contiguous prefix [0, farthest]. If you can reach index i, you can reach every index below it, so all the information about “everything reachable so far” collapses to one number: the maximum reachable index, farthest. Scanning left to right, index i must be within reach (i <= farthest); if it is, extend the frontier to max(farthest, i + nums[i]). Taking the maximum reach at every reachable index is optimal because a larger frontier includes every index a smaller one would, so there is no downside to reaching farther. Once i exceeds farthest, a gap of unreachable indices has opened and nothing after it can be reached.

from typing import List

def canJump(nums: List[int]) -> bool:
    farthest = 0
    last = len(nums) - 1
    for i in range(len(nums)):
        if i > farthest:            # fell into an unreachable gap
            return False
        farthest = max(farthest, i + nums[i])
        if farthest >= last:
            return True
    return True

Walkthrough on nums = [3,2,1,0,4]:

1. i=0: 0 <= 0 ok. farthest = max(0, 0+3) = 3. Not yet >= 4.
2. i=1: 1 <= 3 ok. farthest = max(3, 1+2) = 3.
3. i=2: 2 <= 3 ok. farthest = max(3, 2+1) = 3.
4. i=3: 3 <= 3 ok. farthest = max(3, 3+0) = 3.
5. i=4: 4 > 3, so i fell into the gap; return False.

And on nums = [2,3,1,1,4]: frontier grows 2 → 4 at i=1 (1+3), which is >= 4, so return True.

Complexity: O(n) time, O(1) space.

Approach 3 — Backward greedy: shrink the goalpost

The insight: work right to left. Keep the leftmost index good from which the end is reachable, starting at the last index. Index i is “good” if it can jump to a good index (i + nums[i] >= good); if so, move the goalpost to i. The start is reachable iff good == 0 at the end.

from typing import List

def canJump(nums: List[int]) -> bool:
    good = len(nums) - 1
    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= good:
            good = i
    return good == 0

Complexity: O(n) time, O(1) space. This is the mirror image of the forward greedy and equally valid; pick whichever reads more clearly.

Common pitfalls

• Returning False too eagerly on seeing a 0. A 0 is only fatal if no earlier jump can clear it; the frontier check handles this correctly.
• Off-by-one on the target: reaching farthest >= len(nums) - 1 (the last index), not len(nums).
• Iterating past the frontier without the i > farthest guard — you would read indices that are actually unreachable and wrongly extend the frontier.

Pattern takeaway

When reachability (or any property) is monotone/contiguous, collapse “all states reachable so far” into one boundary value and extend it greedily. Reaching as far as possible at each step is safe precisely because a larger frontier dominates a smaller one.