LeetCode 45 - Jump Game II

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem gives an array nums where each value represents the maximum distance you can jump forward from that position. You start at index 0, and your goal is to reach the final index using the minimum number of jumps possible.

For example, if nums[i] = 3, then from index i you may jump:

1 step forward
2 steps forward
3 steps forward

You are not required to use the full jump distance. Any value from 0 to nums[i] is allowed, as long as the resulting index remains inside the array.

The task is not to determine whether the last index is reachable. The problem guarantees that reaching the last index is always possible. Instead, the challenge is to compute the smallest number of jumps required.

The constraints are important:

nums.length can be as large as 10^4
nums[i] can be up to 1000

A brute force solution that explores every possible jump path quickly becomes too slow because the number of paths grows exponentially. This strongly suggests that we need a more efficient strategy.

There are several important edge cases to keep in mind:

An array of length 1, such as [0], already starts at the destination, so the answer is 0.
Large jump values may allow reaching the end immediately.
Some positions may contain 0, meaning you cannot move forward from that index. However, the problem guarantees the overall array is still solvable.
Multiple paths may exist, but we only care about the minimum number of jumps.

The key challenge is choosing jumps strategically so that we minimize the total number of moves rather than greedily taking the largest immediate jump.

Approaches

Brute Force Approach

A straightforward approach is to recursively try every possible jump from every position.

From index i, we can try jumping to:

i + 1
i + 2
...
i + nums[i]

For each possible next position, we recursively compute the minimum jumps needed to reach the end.

This approach is correct because it explores every valid path and selects the smallest number of jumps among them. However, it is extremely inefficient because many subproblems are recomputed repeatedly.

For example, multiple paths may eventually reach the same index, causing redundant calculations. In the worst case, the recursion tree becomes exponential.

Dynamic programming can reduce this redundancy, but even a DP solution may still require checking many transitions between indices, resulting in O(n^2) complexity.

Optimal Greedy Approach

The key observation is that we do not actually need to explore every path individually.

Instead, we can think about the problem similarly to breadth first search on ranges of indices.

Suppose we already know all positions reachable using the current number of jumps. While scanning those positions, we compute the farthest position reachable with one additional jump.

Once we finish scanning the current reachable range, we must take another jump. At that moment, we update the range to the farthest position discovered.

This greedy strategy works because:

Every position inside the current range is reachable using the same number of jumps.
When choosing the next jump, the only thing that matters is how far we can extend our reach.
Delaying the jump decision until the current range is exhausted guarantees the minimum number of jumps.

This produces an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores all jump combinations
Dynamic Programming	O(n^2)	O(n)	Stores minimum jumps for each index
Optimal Greedy	O(n)	O(1)	Expands reachable ranges greedily

Algorithm Walkthrough

Greedy Range Expansion Algorithm

Initialize three variables:

jumps to count how many jumps we have used
current_end to represent the farthest index reachable using the current number of jumps
farthest to track the farthest index we can reach while scanning the current range

Iterate through the array from index 0 to n - 2.

We stop before the final index because once we can reach the last position, no further jump is necessary. 3. At each index i, compute:

i + nums[i]

This represents the farthest position reachable from index i. 4. Update farthest with the maximum reachable position seen so far.

This means we are collecting all possible destinations reachable with one more jump. 5. When i reaches current_end, we have finished scanning the current jump range.

At this point:

We must take another jump
Increment jumps
Update current_end = farthest

Continue scanning until the loop ends.
Return jumps.

Why it works

The algorithm maintains an important invariant:

Every index up to current_end is reachable using exactly jumps jumps.
While scanning this range, farthest records the best possible extension for the next jump.

When we reach the end of the current range, we are forced to take another jump. Choosing the farthest reachable extension ensures we maximize future reach while still using the minimum number of jumps.

This is effectively a level by level breadth first traversal over reachable ranges, which guarantees optimality.

Python Solution

from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)

        # Already at the destination
        if n == 1:
            return 0

        jumps = 0
        current_end = 0
        farthest = 0

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

            # End of current jump range
            if i == current_end:
                jumps += 1
                current_end = farthest

        return jumps

The implementation follows the greedy range expansion strategy exactly.

The variable jumps stores the minimum number of jumps used so far. The variable current_end represents the boundary of the current reachable range. Every index up to this boundary can be reached using the current number of jumps.

As the loop scans indices inside the current range, the algorithm continuously updates farthest, which tracks the best possible reach for the next jump.

Whenever the loop index reaches current_end, it means the current jump can no longer take us further. At that point, another jump becomes necessary, so we increment jumps and extend the reachable range to farthest.

The loop only runs until n - 2 because once we can reach the last index, no additional jump is needed from the destination itself.

Go Solution

func jump(nums []int) int {
    n := len(nums)

    // Already at the destination
    if n == 1 {
        return 0
    }

    jumps := 0
    currentEnd := 0
    farthest := 0

    for i := 0; i < n-1; i++ {
        if i+nums[i] > farthest {
            farthest = i + nums[i]
        }

        // End of current jump range
        if i == currentEnd {
            jumps++
            currentEnd = farthest
        }
    }

    return jumps
}

The Go implementation is almost identical to the Python version.

Go does not have Python's built in max function for integers, so we update farthest using a simple conditional comparison.

Slices in Go naturally handle dynamic array access similarly to Python lists, so no additional handling is required. Integer overflow is not a concern because the constraints are small.

Worked Examples

Example 1

Input:

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

Initial state:

Variable	Value
jumps	0
current_end	0
farthest	0

Iteration Walkthrough

i	nums[i]	i + nums[i]	farthest	current_end	jumps	Action
0	2	2	2	0	0	Reached current_end
0	2	2	2	2	1	Take first jump
1	3	4	4	2	1	Expand farthest reach
2	1	3	4	2	1	Reached current_end
2	1	3	4	4	2	Take second jump

The algorithm returns 2.

Optimal path:

0 -> 1 -> 4

Example 2

Input:

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

Initial state:

Variable	Value
jumps	0
current_end	0
farthest	0

Iteration Walkthrough

i	nums[i]	i + nums[i]	farthest	current_end	jumps	Action
0	2	2	2	0	0	Reached current_end
0	2	2	2	2	1	Take first jump
1	3	4	4	2	1	Expand reach
2	0	2	4	2	1	Reached current_end
2	0	2	4	4	2	Take second jump

The algorithm returns 2.

Even though index 2 contains 0, the algorithm already discovered a farther reachable position through index 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is processed exactly once
Space	O(1)	Only a few integer variables are used

The greedy algorithm performs a single pass through the array. Every iteration does constant work, so the total runtime grows linearly with the input size.

The algorithm uses only three additional integer variables regardless of input size, so the extra space usage is constant.

Test Cases

from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)

        if n == 1:
            return 0

        jumps = 0
        current_end = 0
        farthest = 0

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

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

        return jumps

solution = Solution()

assert solution.jump([2, 3, 1, 1, 4]) == 2  # Standard example
assert solution.jump([2, 3, 0, 1, 4]) == 2  # Contains zero but still reachable
assert solution.jump([0]) == 0  # Single element array
assert solution.jump([1, 2]) == 1  # One direct jump
assert solution.jump([10, 1, 1, 1]) == 1  # Large first jump reaches end
assert solution.jump([1, 1, 1, 1]) == 3  # Must move one step each time
assert solution.jump([2, 1]) == 1  # Minimal non-trivial case
assert solution.jump([3, 2, 1]) == 1  # Direct reach from first index
assert solution.jump([1, 2, 3]) == 2  # Requires careful range expansion
assert solution.jump([2, 0, 2, 0, 1]) == 2  # Multiple zeros

Test	Why
`[2,3,1,1,4]`	Standard example with multiple choices
`[2,3,0,1,4]`	Verifies handling of zeros
`[0]`	Single element edge case
`[1,2]`	Smallest array requiring one jump
`[10,1,1,1]`	Large jump immediately reaches end
`[1,1,1,1]`	Requires maximum number of sequential jumps
`[2,1]`	Minimal reachable two-element array
`[3,2,1]`	First jump already reaches destination
`[1,2,3]`	Tests range boundary updates
`[2,0,2,0,1]`	Verifies greedy expansion across blocked positions

Edge Cases

Single Element Array

An input like [0] is an important edge case because the starting index is already the destination. A naive implementation might incorrectly count one jump simply because the loop begins processing index 0.

The implementation handles this explicitly with:

if n == 1:
    return 0

This guarantees the correct answer without entering the main loop.

Arrays Containing Zeroes

A value of 0 means no forward movement is possible from that position. This can easily break naive greedy strategies that jump too aggressively without considering future reachability.

For example:

[2,3,0,1,4]

If we land on index 2, we become stuck. However, the optimal strategy avoids that issue by considering the entire reachable range before committing to the next jump.

The greedy algorithm succeeds because it tracks the farthest reachable index across all positions in the current range, not just the current position.

Large Initial Jump

Consider:

[10,1,1,1]

The first index can already reach the last index directly. Some implementations may continue processing unnecessarily or miscount jumps.

The algorithm correctly identifies that the first jump extends the reachable range beyond the end of the array. Only one jump is counted, which is optimal.