DSA Jump Game II

The problem

Jump Game II asks for the fewest jumps that reach the last index of a list. Each value caps how far one jump from its index can go. A jump may land on any index up to that cap.

The answer is a count of jumps, not a path. A list with one element needs zero jumps, because the walk starts on its last index. An unreachable end answers minus one in this article, following the convention of the source lesson.

cases = [
    ([2, 3, 1, 1, 4], 2),
    ([3, 2, 1, 0, 4], -1),
    ([1, 1, 1, 1], 3),
    ([0], 0),
    ([2, 0, 0], 1),
]
for nums, expected in cases:
    print("nums", nums, "-> fewest jumps:", expected)

Read the first row against the second. Both lists have the same shape, but the zero at index 3 blocks the second list completely. The first list needs two jumps, not four, because one jump can pass over indices without landing on them.

Intuition: the longest jump can waste a jump

The first idea jumps as far as possible every time. It worked badly in Jump Game, where it could strand the walk. Here it fails more quietly, by spending one jump too many.

The walk below always takes the longest jump on a seven-value list. It arrives in three jumps. A two-jump path exists through index 3, and the legality of each of its jumps is printed as proof.

nums = [4, 2, 1, 3, 1, 1, 4]
i = 0
path = [0]
while i < len(nums) - 1:
    i = i + nums[i]
    path.append(i)
print("longest-jump path:", path, " jumps:", len(path) - 1)
print("path 0 -> 3 -> 6, each jump legal:", 0 + nums[0] >= 3 and 3 + nums[3] >= 6)

The longest first jump sails past index 3. Index 3 holds the value 3, the one strong landing in the list. Fewest jumps is a question about ranges, not about single heroic leaps.

Brute force: try every path, keep the shortest

The brute force tries every legal jump from every landing, like the brute force in Jump Game. This time it keeps the smallest jump count among all paths that reach the end. A path that never arrives counts for nothing.

The search is recursive and counts its own calls. Each call adds one jump to the path being explored. The count below shows the price of certainty on a five-value list.

def brute_jumps(nums):
    calls = 0
    best = None
    def search(i, jumps):
        nonlocal calls, best
        calls += 1
        if i >= len(nums) - 1:
            if best is None or jumps < best:
                best = jumps
            return
        if nums[i] == 0:
            return
        for step in range(1, nums[i] + 1):
            search(i + step, jumps + 1)
    search(0, 0)
    return (best if best is not None else -1), calls

result, calls = brute_jumps([2, 3, 1, 1, 4])
print("fewest jumps:", result, " search calls:", calls)
result, calls = brute_jumps([1, 1, 1, 1])
print("fewest jumps:", result, " search calls:", calls)

The all-ones list has exactly one path, so its search is cheap. Branching values are what multiply paths. Every added branch re-explores the tail of the list from a new landing.

The optimal solution: count ranges, not landings

A jump range is every index reachable within the current jump count, and the farthest index reachable from inside a range opens the next range, so counting closed ranges counts the jumps. That one sentence is the whole method.

The walk scans indices in order and tracks the farthest reach seen inside the current range. When the scan reaches the end of the range, one jump is spent and the range extends to that farthest reach. A range that cannot grow means the end is unreachable.

def min_jumps(nums):
    if not nums:
        return -1
    if len(nums) == 1:
        return 0
    jumps = 0
    range_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == range_end:
            if farthest == i:
                return -1
            jumps += 1
            range_end = farthest
            if range_end >= len(nums) - 1:
                return jumps
    return jumps

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

All five cases pass. The stalled list returns minus one at the moment a range fails to grow. No path is ever stored, because the range boundary carries everything the count needs.

Walkthrough: two ranges in [2, 3, 1, 1, 4]

The walk scans the first four indices. The state is the current range end, the farthest reach inside it, and the jumps spent. A line prints whenever a range closes.

nums = [2, 3, 1, 1, 4]
jumps = 0
range_end = 0
farthest = 0
for i in range(len(nums) - 1):
    farthest = max(farthest, i + nums[i])
    print("index", i, "value", nums[i], "- farthest so far:", farthest)
    if i == range_end:
        jumps += 1
        range_end = farthest
        print("range closed - jumps:", jumps, "- next range ends at:", range_end)
print("answer:", jumps)

The first range holds only index 0, and it opens the range ending at index 2. Inside that range, index 1 reaches index 4. The second range therefore closes on the last index, and the answer is two.

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 range 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 range walk stores three numbers, 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), " range visits:", n - 1)

The pattern matches Jump Game exactly, because the brute force is the same search with a counter added. Ten values cost 143 calls against 9 range visits. The range method never pays for a path it does not take.

Edge cases and pitfalls

Counting visited indices as jumps is the classic off-by-one mistake. The list [1, 1, 1, 1] visits four indices and needs three jumps. A jump is spent when a range closes, not when an index is scanned.

An empty list has no last index, so it answers minus one in this article. A single element answers zero. Both conventions match the reachability answers of Jump Game, where the same empty list answers False.

def min_jumps(nums):
    if not nums:
        return -1
    if len(nums) == 1:
        return 0
    jumps = 0
    range_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == range_end:
            if farthest == i:
                return -1
            jumps += 1
            range_end = farthest
            if range_end >= len(nums) - 1:
                return jumps
    return jumps

print("empty list:", min_jumps([]))
print("single zero:", min_jumps([0]))
print("zero at the start:", min_jumps([0, 1]))
print("one jump clears all:", min_jumps([5, 1, 1]))
print("zero cleared from index 0:", min_jumps([2, 0, 0]))
print("zero as a wall:", min_jumps([1, 0, 1]))
print("indices visited in [1, 1, 1, 1]:", 4, " jumps needed:", min_jumps([1, 1, 1, 1]))

The wall row returns minus one because its only range cannot grow past index 1. The clears-all row spends one jump, because the first range already ends past the last index. Range boundaries, not values alone, decide both rows.