Jump Game

Jump Game is the cleanest greedy problem there is. The simple approach explores paths; the greedy one keeps a single number and never looks back. If you can explain why that single number is enough, you understand the pattern.

It is also the first of a family. Jump Game II, video stitching and "minimum taps to water a garden" all reuse the same idea of a furthest reach.

The problem

You stand on index 0 of an array of non-negative integers. The value at an index is the longest jump you may make from there: from index i you may move to any index from i + 1 up to i + nums[i]. A value of 0 means you are stuck on that index. Return whether you can land on the last index.

• [2, 3, 1, 1, 4] → True. Jump from 0 to 1, then from 1 (value 3) straight to 4.
• [3, 2, 1, 0, 4] → False. Every path lands on index 3, whose value is 0, and nothing reaches past it.

Constraints: 1 ≤ n ≤ 10⁵, and 0 ≤ nums[i] ≤ 10⁵.

Clarifying questions

• Can I jump shorter than the value? Yes — any length from 1 up to it. (If jumps were exact, this would be a graph search; see the follow-ups.)
• If the array has one element? You are already on the last index: True.
• Can values be negative? No.
• Do you want the path or just yes/no? Just yes/no.

Approach 1: the simple way

Mark index 0 as reachable. Walk left to right; from every reachable index, mark every index it can jump to.

1def can_jump_brute(nums: list[int]) -> bool:2    """Mark every index each reachable index can land on."""3    n = len(nums)4    reachable = [False] * n5    reachable[0] = True6    for i in range(n):7        if not reachable[i]:8            continue9        for step in range(1, nums[i] + 1):10            if i + step < n:11                reachable[i + step] = True12    return reachable[n - 1]

This is correct, and it is O(n × max jump) time — O(n²) when the values are large — with O(n) space. With n = 10⁵ and every value around 10⁵, the inner loop runs up to 10¹⁰ times. It marks the same indices over and over: index 50 might be marked by forty different earlier indices. Recursion that tries every path is worse still — exponential.

The key insight

Look at what the reachable array actually looks like. It is never scattered. It is always a block of True starting at index 0, followed by False.

Why? Suppose you can reach index i. You got there by jumping from some earlier index k whose jump covers i. That same jump could have stopped short at any index between k and i — jumps can be shorter. So every index before i is reachable too. Reachability has no holes.

A block with no holes is described completely by where it ends. So the whole reachable array collapses into one number: the furthest index reachable so far. Walk left to right. If the current index is inside the block, extend the block with i + nums[i]. If the current index is past the end of the block, nothing before it could reach it, and nothing after it can either, because you can never get there to jump from it.

That is the greedy choice: you never decide which jump to take. You only track the best reach any of them gives.

Approach 2: optimised — the furthest reach

1def can_jump(nums: list[int]) -> bool:2    """Walk left to right, keeping the furthest index reachable so far."""3    furthest = 04    for i, jump in enumerate(nums):5        if i > furthest:               # no earlier index reaches i6            return False7        furthest = max(furthest, i + jump)8    return True

1. furthest = 0: at the start, only index 0 is in the block.
2. Check i > furthest before using index i. An index you cannot stand on gives you nothing.
3. Extend the block with i + jump.
4. If the loop finishes, every index — including the last — was inside the block.

Dry run on [2, 3, 1, 1, 4]:

The loop finishes: True. Now [3, 2, 1, 0, 4]:

Every index before 4 reaches exactly index 3, and index 3 is stuck.

Complexity: O(n) time — one pass, O(1) work per index. O(1) space — one integer. You can also return True early as soon as furthest >= len(nums) - 1; it does not change the bound.

Approach 3: the same idea, backwards

Walk from the right. Keep a goal: the leftmost index known to reach the end. If index i can jump to the goal, then i becomes the new goal. At the end, ask whether the goal moved all the way to 0.

1def can_jump_backward(nums: list[int]) -> bool:2    """Walk right to left, moving the goal whenever an index can reach it."""3    goal = len(nums) - 14    for i in range(len(nums) - 2, -1, -1):5        if i + nums[i] >= goal:        # from i we can reach the goal, so i is the new goal6            goal = i7    return goal == 0

On [2, 3, 1, 1, 4] the goal moves 4 → 3 → 2 → 1 → 0: True. On [3, 2, 1, 0, 4] no index reaches 4, so the goal stays at 4: False. Same O(n) time and O(1) space. It is worth knowing because it answers a different question for free: every index where the goal moved is a "good" starting index.

Edge cases

• One element, [0]: the loop checks index 0 (not past 0) and finishes: True. You are already there.
• Stuck at the start, [0, 1]: index 1 is past furthest = 0: False.
• A zero you can jump over, [2, 0, 0]: index 0 reaches 2 directly, so the zeros never matter: True.
• Huge values: i + jump can exceed the array; that is fine, it only means "the end is reachable".

Follow-ups

• Fewest jumps to reach the end? That is Jump Game II, the next lesson: the same furthest reach, counted in levels.
• Jumps must be exactly nums[i], left or right, and you want to reach any zero? The block argument breaks, because you cannot stop short. Use breadth-first search over indices, O(n).
• Each landing has a cost and you want the cheapest path? Greedy no longer applies; it is DP, or a sliding-window minimum for the O(n) version.