LeetCode 45: Jump Game II

Problem Restatement

We are given a 0-indexed integer array nums.

We start at index 0.

Each value nums[i] tells us the maximum jump length from index i. From index i, we may jump to any index from i + 1 up to i + nums[i], as long as the index is inside the array.

We need to return the minimum number of jumps needed to reach the last index.

The test cases guarantee that the last index is reachable.

Example:

nums = [2, 3, 1, 1, 4]

The answer is:

2

One optimal path is:

0 -> 1 -> 4

From index 0, jump to index 1.

From index 1, jump to the last index.

Another example:

nums = [2, 3, 0, 1, 4]

The answer is also:

2

Input and Output

Function shape:

def jump(nums: list[int]) -> int:
    ...

First Thought: Dynamic Programming

A direct way is to define:

dp[i] = minimum jumps needed to reach index i

Start with:

dp[0] = 0

Then for every index i, try all jumps from i.

If we can jump from i to j, update:

dp[j] = min(dp[j], dp[i] + 1)

This works, but it can be slow.

In the worst case, each index can jump to many later indices, so this approach can take O(n^2) time.

We need a linear approach.

Key Insight

Think of jumps as ranges.

After 0 jumps, we are at index 0.

After 1 jump, we can reach every index from 1 up to nums[0].

While scanning this current reachable range, we compute the farthest index reachable with one more jump.

When we finish scanning the current range, we must make another jump.

So we track three values:

This is like breadth-first search over ranges, but without an explicit queue.

Algorithm

Initialize:

jumps = 0
current_end = 0
farthest = 0

Scan indices from 0 to len(nums) - 2.

We stop before the last index because once we can reach the last index, no further jump is needed from it.

At each index i, update:

farthest = max(farthest, i + nums[i])

This means: from all positions inside the current jump range, what is the farthest next position we can reach?

If we reach the end of the current range:

if i == current_end:

then we need to commit to another jump:

jumps += 1
current_end = farthest

At the end, return jumps.

Walkthrough

Use:

nums = [2, 3, 1, 1, 4]

Start:

jumps = 0
current_end = 0
farthest = 0

At index 0:

farthest = max(0, 0 + 2) = 2

Now i == current_end, so we have finished the range reachable with 0 jumps.

We make one jump:

jumps = 1
current_end = 2

This means with 1 jump, we can reach any index up to 2.

Now scan indices 1 and 2 to find the best range for the next jump.

At index 1:

farthest = max(2, 1 + 3) = 4

At index 2:

farthest = max(4, 2 + 1) = 4

Now i == current_end, so we have finished the range reachable with 1 jump.

We make another jump:

jumps = 2
current_end = 4

Index 4 is the last index, so the answer is:

2

Correctness

The algorithm processes the array in ranges.

At any moment, current_end marks the farthest index reachable using exactly jumps jumps or fewer. Every index up to current_end is part of the current reachable layer.

While scanning this layer, the algorithm computes farthest, the farthest index reachable using one additional jump from any index in the layer.

When the scan reaches current_end, all choices for the current number of jumps have been considered. To go farther, one more jump is necessary. Updating current_end = farthest creates the next reachable layer.

Because the algorithm only increases jumps after exhausting all positions reachable with the previous number of jumps, the first time the range reaches the last index, it has used the minimum possible number of jumps.

The problem guarantees reachability, so the process always reaches the last index.

Complexity

Implementation

class Solution:
    def jump(self, nums: list[int]) -> int:
        jumps = 0
        current_end = 0
        farthest = 0

        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])

            if i == current_end:
                jumps += 1
                current_end = farthest

        return jumps

Code Explanation

We begin with no jumps:

jumps = 0

At the start, the current reachable range ends at index 0:

current_end = 0

The best next reach also starts at 0:

farthest = 0

Then we scan up to the second-to-last index:

for i in range(len(nums) - 1):

We do not need to jump from the last index.

At each index, we update the farthest place reachable by one more jump:

farthest = max(farthest, i + nums[i])

When we reach the boundary of the current jump range:

if i == current_end:

we must use another jump:

jumps += 1
current_end = farthest

At the end, jumps is the minimum number of jumps needed to reach the last index.

Testing

def run_tests():
    s = Solution()

    assert s.jump([2, 3, 1, 1, 4]) == 2
    assert s.jump([2, 3, 0, 1, 4]) == 2
    assert s.jump([0]) == 0
    assert s.jump([1, 2]) == 1
    assert s.jump([1, 1, 1, 1]) == 3
    assert s.jump([4, 1, 1, 1, 1]) == 1
    assert s.jump([2, 1, 1, 1, 1]) == 3

    print("all tests passed")

run_tests()