DSA Jump Game

The problem

Jump Game asks whether the last index of a list can be reached from the first index. Each value caps how far one jump from its index can go. A jump may land on any index up to that cap, not only on the farthest one.

The answer is True or False. Reaching the last index exactly and jumping past it both count as success. The cases below include a list that stalls one index short of the end.

cases = [
    ([2, 3, 1, 1, 4], True),
    ([3, 2, 1, 0, 4], False),
    ([1, 1, 1, 1], True),
    ([0], True),
    ([2, 0, 0], True),
]
for nums, expected in cases:
    print("nums", nums, "-> can reach the end:", expected)

Read the second row carefully. The values 3, 2 and 1 carry the walk to index 3. The value there is 0, and no earlier jump clears it, so the last index stays out of reach.

Intuition: the longest jump is not always the right jump

The first idea jumps as far as possible every time. A long jump feels like pure progress. The feeling hides a trap, because the farthest landing spot can be a dead end.

A shorter jump can land on the one index with a strong value. The walk below takes the longest jump from index 0 and strands itself. The end of this same list is reachable through index 3.

nums = [4, 0, 0, 2, 0, 5]
i = 0
visited = [0]
while i < len(nums) - 1 and nums[i] > 0:
    i = i + nums[i]
    visited.append(i)
print("longest-jump path:", visited)
print("last index reached:", visited[-1] == len(nums) - 1)
print("shorter path 0 -> 3 -> 5 is legal:", 0 + nums[0] >= 3 and 3 + nums[3] >= 5)

The longest jump lands on index 4, which holds 0. The shorter jump to index 3 holds the value 2, and 2 carries the walk to the end. Choosing single jumps is the wrong frame entirely.

Brute force: try every jump from every landing

The brute force keeps the choosing frame and removes the guessing. From each landing it tries every legal jump length. A path that reaches the last index settles the answer.

The search is recursive and counts its own calls. A landing on the last index returns True at once. A zero value returns False, because no jump leaves it.

def can_brute(nums):
    calls = 0
    def search(i):
        nonlocal calls
        calls += 1
        if i >= len(nums) - 1:
            return True
        if nums[i] == 0:
            return False
        for step in range(1, nums[i] + 1):
            if search(i + step):
                return True
        return False
    return search(0), calls

result, calls = can_brute([2, 3, 1, 1, 4])
print("reachable:", result, " search calls:", calls)
result, calls = can_brute([3, 2, 1, 0, 4])
print("reachable:", result, " search calls:", calls)

The stalled list costs more calls than the reachable one. Only exhausting every path proves that no route exists. Bad news is the expensive answer again, and longer lists multiply the paths.

The optimal solution: carry the farthest reach

Reach is the farthest index known to be reachable so far, and one walk that extends the reach at every index inside it answers the question with no choices at all. That one sentence is the whole method.

Every index up to the reach can be landed on. Such an index offers a candidate reach of its position plus its value. The reach keeps the largest candidate and never moves backward. An index past the reach ends the walk in failure.

def can_jump(nums):
    if not nums:
        return False
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return reach >= len(nums) - 1

cases = [
    ([2, 3, 1, 1, 4], True),
    ([3, 2, 1, 0, 4], False),
    ([1, 1, 1, 1], True),
    ([0], True),
    ([2, 0, 0], True),
]
for nums, expected in cases:
    result = can_jump(nums)
    print("nums", nums, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. The trap list from the intuition section also passes this walk, because the reach from index 0 already covers index 3. No landing spot is ever chosen, so no landing spot can be chosen wrong.

Walkthrough: reach through [2, 3, 1, 1, 4]

The walk visits one index at a time. The state is the single reach value after each index. Each line shows the candidate that index offered and the reach it left behind.

nums = [2, 3, 1, 1, 4]
reach = 0
for i, step in enumerate(nums):
    reach = max(reach, i + step)
    print("index", i, "value", step, "- candidate:", i + step, "- reach:", reach)
print("last index:", len(nums) - 1, "reached:", reach >= len(nums) - 1)

Index 1 does the heavy lifting. Its candidate 4 lands exactly on the last index. Every later line confirms the reach never falls back, and the answer is read off the final comparison.

Complexity

The brute force explores combinations of jump choices, so its call count grows exponentially in the worst case, as the counts below show. The reach walk visits each index once, so its time is O(n).

The brute force recursion stack can grow to the length of one path, so its extra space is O(n). The reach walk stores one number, so its extra space is O(1).

def count_calls(n):
    nums = [2] * n
    calls = 0
    def paths(i):
        nonlocal calls
        calls += 1
        if i >= n - 1:
            return 1
        total = 0
        for step in range(1, nums[i] + 1):
            if i + step < n:
                total += paths(i + step)
        return total
    paths(0)
    return calls

for n in [6, 8, 10]:
    print("values", n, "- brute search calls:", count_calls(n), " reach visits:", n)

The brute counts above explore every path on lists of 2s. Ten values already cost 143 calls against 10 visits. The reach walk pays for no path at all, only for the frontier.

Edge cases and pitfalls

A zero value is only a wall when no earlier jump clears it. Treating any zero as instant failure is the classic mistake. The list [2, 0, 0] holds a zero at index 1, and its answer is still True.

An empty list has no last index, so it answers False in this article. A list holding one zero starts on its own last index, so it answers True. Both rows run below.

def can_jump(nums):
    if not nums:
        return False
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return reach >= len(nums) - 1

def can_jump_zero_bug(nums):
    for i, step in enumerate(nums):
        if step == 0 and i < len(nums) - 1:
            return False
    return True

print("empty list:", can_jump([]))
print("single zero:", can_jump([0]))
print("zero at the start:", can_jump([0, 1]))
print("zero cleared from index 0:", can_jump([2, 0, 0]))
print("zero as a wall:", can_jump([1, 0, 1]))
print("one jump clears all:", can_jump([5, 0, 0, 0, 0]))
print("zero bug on [2, 0, 0]:", can_jump_zero_bug([2, 0, 0]), " correct:", can_jump([2, 0, 0]))

The buggy variant fails exactly the row the reach walk gets right. The reach already covers the zero at index 1 in that row. A zero matters only when the walk must land on it with nothing beyond it.