Jump Game Explained: Greedy Farthest Reach in One Pass

Jump game is a problem where the obvious approach, exploring the jumps, is correct but slow, and the fast approach looks too simple to be right. You do not need to know which route reaches the end, or even whether any particular jump is a good idea. You need one number: the farthest index you could possibly stand on so far. This article explains why that number is enough, extends it to the "fewest jumps" version, and checks both against an exhaustive search.

The problem it solves

You start on index 0 of an array of non-negative integers. The value at each index is the maximum jump length from there: from index i with value v you may land anywhere from i + 1 to i + v. Can you reach the last index?

• [2, 3, 1, 1, 4]: yes. Jump 1 step to index 1, then 3 steps to the end.
• [3, 2, 1, 0, 4]: no. Every route lands on index 3, whose value is 0, and nothing jumps over it.

Exploring every route is exponential in the worst case. A dynamic-programming table that marks each index reachable or not is O(n²). The greedy is O(n) time and O(1) space.

The intuition

Here is the observation that removes the routes: the reachable indices always form a prefix of the array. If you can stand on index j, you can stand on every index before it too, because whatever jump carried you past an index could have been shortened to land on it. Jump lengths are maximums, not exact values.

So "which indices are reachable" is described completely by one number, reach, the largest reachable index. Walk left to right. At each index i:

• If i > reach, index i is not in the prefix. Nothing before it could get here, and nothing after it is reachable either. The answer is no.
• Otherwise i is reachable, and from it you could get as far as i + nums[i]. Set reach = max(reach, i + nums[i]).

If the walk gets through the array, or reach touches the last index, the answer is yes. The frontier never shrinks, and each index is examined once.

The same prefix view solves the harder version, the fewest jumps to the end. Think of it as breadth-first search where each level is a contiguous range: the indices reachable in one jump, then the ones reachable in two, and so on. Scan the current range, track the farthest index it can reach, and when the scan passes the end of the range, that farthest index becomes the end of the next range and the jump count goes up by one.

Watch it run

The animation runs both arrays, drawing the reachable prefix as a band under the row. On [2, 3, 1, 1, 4] the frontier starts at 0. From index 0 you may hop 2, so it stretches to index 2. Index 1 offers 1 + 3 = 4, and the frontier snaps straight to the last index. At index 2, 2 + 1 = 3 does not beat 4, so the frontier holds: it only ever grows. The walk reaches the end without once stepping outside the band: yes.

Then one cell changes to 0: [3, 2, 1, 0, 4]. Index 0 hops 3, and nothing inside that band can push the frontier past it. Index 3 holds a zero, so the frontier is stuck at 3. Index 4 sits past the frontier, so it can never be stepped on, whatever its own value says: no.

The code

The lesson's scan, and the fewest-jumps version built on the same frontier:

def can_finish(nums):
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:                        # outside the reachable prefix
            return False
        reach = max(reach, i + jump)         # furthest index now in range
    return True

def min_jumps(nums):
    jumps, end, farthest = 0, 0, 0           # [.., end] is reachable in `jumps` jumps
    for i in range(len(nums) - 1):
        if i > farthest:
            return -1                        # the end is unreachable
        farthest = max(farthest, i + nums[i])
        if i == end:                         # this level is used up: jump once more
            jumps, end = jumps + 1, farthest
    return jumps if end >= len(nums) - 1 else -1

print(can_finish([2, 3, 1, 1, 4]), can_finish([3, 2, 1, 0, 4]))   # True False
print(min_jumps([2, 3, 1, 1, 4]), min_jumps([2, 3, 0, 1, 4]))     # 2 2
print(min_jumps([0]), min_jumps([3, 2, 1, 0, 4]))                 # 0 -1

Both against a breadth-first search over the indices, which tries every jump length from every index, on 3,000 random arrays with plenty of zeros:

import random
from collections import deque

def bfs_jumps(nums):
    dist = {0: 0}
    queue = deque([0])
    while queue:
        i = queue.popleft()
        for j in range(i + 1, min(i + nums[i], len(nums) - 1) + 1):
            if j not in dist:
                dist[j] = dist[i] + 1
                queue.append(j)
    return dist.get(len(nums) - 1, -1)

random.seed(17)
ok = True
for _ in range(3000):
    nums = [random.choice([0, 0, 1, 2, 3]) for _ in range(random.randint(1, 12))]
    expected = bfs_jumps(nums)
    ok &= can_finish(nums) == (expected != -1)
    ok &= min_jumps(nums) == expected
print(ok)                                    # True

The complexity

• Exploring routes recursively: exponential without memoization.
• Reachability table: mark index 0, then from every marked index mark the next nums[i] indices. O(n²) in the worst case, O(n) space.
• Greedy frontier: O(n) time, O(1) space, for both the yes-or-no and the fewest-jumps versions.

Where it goes wrong

• Treating values as exact jump lengths. The whole argument rests on "at most". With exact lengths the reachable set is not a prefix and you need the search.
• Checking i > reach after updating. The check must come first; otherwise an unreachable index can extend the frontier with its own value.
• Greedily taking the longest jump. From index 0 of [2, 3, 1, 1, 4] the longest jump lands on index 2, value 1, and it only happens to work because index 2 can still reach index 3. On [2, 3, 1, 0, 4] it lands on index 2, steps to the zero at index 3 and gets stuck, while the shorter jump to index 1 reaches the end.
• Looping to the last index in min_jumps. Standing on the last index needs no further jump; scanning it can add one spurious jump.
• A single-element array. You are already at the end: reachable, zero jumps.

When it shows up in interviews

The reachability version is a common medium and the minimum-jumps version a common follow-up, usually in the greedy section. Interviewers often let you start with the O(n²) table and then ask whether you really need all of it, which is the cue for the prefix argument. Close relatives: jump game III, where you jump exactly nums[i] left or right and need a real BFS or DFS, and the video-stitching and minimum-taps problems, which are the fewest-jumps scan applied to intervals.

How to say it in an interview

"Because each value is a maximum jump, the reachable indices always form a prefix, so I only track the largest reachable index. I scan left to right; if the current index is beyond it, the end is unreachable, otherwise I extend it with i + nums[i]. That is O(n) and O(1). For the fewest jumps I do the same scan in levels, like BFS: when I pass the end of the current level, the farthest index seen becomes the next level's end and I count one jump."

The same "carry one number" greedy shows up in the gas station problem, and why greedy is allowed at all is the subject of what makes greedy work.