Jump Game — InterviewPrepKit

Solving tips

Key insight: reachable indices form a contiguous prefix [0, farthest], so collapse all state into one number — the farthest reachable index.
Scan left to right; if index i ever exceeds farthest you've hit an unreachable gap and can return False immediately.
At each reachable i, extend farthest = max(farthest, i + nums[i]); return True once farthest reaches the last index.
Target O(n) time and O(1) space; don't panic on seeing a 0 — it's only fatal if no earlier jump vaults over it, which the frontier check handles.

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 the traps that make it non-trivial.

Think about it first

Hint 1

You do not need to know how you get somewhere, only whether it is reachable. As you move left to right, what single number summarizes everything reachable so far?

Hint 2

Track the farthest index reachable. At each position i, first check: is i itself within the current reach? If not, you are stuck and can never proceed.

Hint 3

If i is reachable, update the frontier to max(farthest, i + nums[i]). If the frontier ever reaches or passes the last index, return True.

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

class Solution:
    def canJump(self, 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 too (just stop short). So all the information you need about “everything reachable so far” collapses to a single number: the maximum index you can reach, farthest. Scanning left to right, at each index i you only need it to be within reach (i <= farthest); if so, greedily extend the frontier to max(farthest, i + nums[i]). Taking the maximum reach at every reachable cell is optimal because a larger frontier can only ever include the same-or-more indices — there is no downside to reaching farther, and no cleverer choice of intermediate landings could reach an index the frontier cannot. The moment i exceeds farthest, a gap of unreachable cells has opened and nothing after it can be reached.

from typing import List

class Solution:
    def canJump(self, 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]:

i=0: 0 <= 0 ok. farthest = max(0, 0+3) = 3. Not yet >= 4.
i=1: 1 <= 3 ok. farthest = max(3, 1+2) = 3.
i=2: 2 <= 3 ok. farthest = max(3, 2+1) = 3.
i=3: 3 <= 3 ok. farthest = max(3, 3+0) = 3.
i=4: 4 > 3 → 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

class Solution:
    def canJump(self, 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 — the mirror image of the forward greedy, equally valid; pick whichever reads more clearly to you.

Common pitfalls

Returning False too eagerly on seeing a 0. A 0 is only fatal if no earlier jump can vault over 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.