Jump Game II

Given an array where each element represents the maximum jump length, find the minimum number of jumps to reach the last index

Language Selection

Choose your preferred programming language

Showing: Python

Jump Game II

Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where 0 <= j <= nums[i] and i + j < n.

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can always reach nums[n - 1].

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It is guaranteed that you can reach nums[n - 1]

Examples:

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 3:

Input: nums = [1,1,1,1]
Output: 3
Explanation: Jump 1 step at a time: 0 -> 1 -> 2 -> 3.

Example 4:

Input: nums = [10,1,1,1,1]
Output: 1
Explanation: Jump directly from index 0 to index 4.

Approach 1: BFS (Level-Order Traversal)

Algorithm:

  1. Treat the array as a graph where each index can reach a range of subsequent indices
  2. Perform BFS where each “level” represents one jump
  3. For each level, find the furthest index reachable from all positions in the current level
  4. The number of levels traversed to reach the last index is the answer

Time Complexity: O(n) Space Complexity: O(1)

Python:

def jump(nums):
    """
    Find minimum jumps using BFS level-order traversal
    Time: O(n)
    Space: O(1)
    """
    n = len(nums)
    if n <= 1:
        return 0

    jumps = 0
    current_end = 0  # end of current BFS level
    farthest = 0     # farthest reachable from current level

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

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

            if current_end >= n - 1:
                break

    return jumps

Java:

class Solution {
    /**
     * Find minimum jumps using BFS level-order traversal
     * Time: O(n)
     * Space: O(1)
     */
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;

        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;

        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);

            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;

                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }

        return jumps;
    }
}

Go:

// jump - Find minimum jumps using BFS level-order traversal
// Time: O(n)
// Space: O(1)
func jump(nums []int) int {
    n := len(nums)
    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]
        }

        if i == currentEnd {
            jumps++
            currentEnd = farthest

            if currentEnd >= n-1 {
                break
            }
        }
    }

    return jumps
}

JavaScript:

/**
 * Find minimum jumps using BFS level-order traversal
 * Time: O(n)
 * Space: O(1)
 */
function jump(nums) {
    const n = nums.length;
    if (n <= 1) return 0;

    let jumps = 0;
    let currentEnd = 0;
    let farthest = 0;

    for (let i = 0; i < n - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);

        if (i === currentEnd) {
            jumps++;
            currentEnd = farthest;

            if (currentEnd >= n - 1) {
                break;
            }
        }
    }

    return jumps;
}

C#:

public class Solution {
    /// <summary>
    /// Find minimum jumps using BFS level-order traversal
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int Jump(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return 0;

        int jumps = 0;
        int currentEnd = 0;
        int farthest = 0;

        for (int i = 0; i < n - 1; i++) {
            farthest = Math.Max(farthest, i + nums[i]);

            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;

                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }

        return jumps;
    }
}

Approach 2: Greedy (Forward Scanning)

Algorithm:

  1. At each jump, scan all positions reachable from the current position
  2. Among those positions, pick the one that lets us reach the furthest after the next jump
  3. This greedy choice guarantees minimizing total jumps
  4. Continue until we reach or exceed the last index

Time Complexity: O(n) Space Complexity: O(1)

Python:

def jump(nums):
    """
    Find minimum jumps using forward-scanning greedy
    Time: O(n)
    Space: O(1)
    """
    n = len(nums)
    if n <= 1:
        return 0

    jumps = 0
    pos = 0

    while pos < n - 1:
        # If current position can reach the end directly
        if pos + nums[pos] >= n - 1:
            jumps += 1
            break

        # Find the next position that maximizes reach
        best_next = pos + 1
        best_reach = 0

        for i in range(pos + 1, min(pos + nums[pos] + 1, n)):
            if i + nums[i] > best_reach:
                best_reach = i + nums[i]
                best_next = i

        pos = best_next
        jumps += 1

    return jumps

Java:

class Solution {
    /**
     * Find minimum jumps using forward-scanning greedy
     * Time: O(n)
     * Space: O(1)
     */
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;

        int jumps = 0;
        int pos = 0;

        while (pos < n - 1) {
            if (pos + nums[pos] >= n - 1) {
                jumps++;
                break;
            }

            int bestNext = pos + 1;
            int bestReach = 0;

            for (int i = pos + 1; i <= Math.min(pos + nums[pos], n - 1); i++) {
                if (i + nums[i] > bestReach) {
                    bestReach = i + nums[i];
                    bestNext = i;
                }
            }

            pos = bestNext;
            jumps++;
        }

        return jumps;
    }
}

Go:

// jump - Find minimum jumps using forward-scanning greedy
// Time: O(n)
// Space: O(1)
func jump(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }

    jumps := 0
    pos := 0

    for pos < n-1 {
        if pos+nums[pos] >= n-1 {
            jumps++
            break
        }

        bestNext := pos + 1
        bestReach := 0
        end := pos + nums[pos]
        if end > n-1 {
            end = n - 1
        }

        for i := pos + 1; i <= end; i++ {
            if i+nums[i] > bestReach {
                bestReach = i + nums[i]
                bestNext = i
            }
        }

        pos = bestNext
        jumps++
    }

    return jumps
}

JavaScript:

/**
 * Find minimum jumps using forward-scanning greedy
 * Time: O(n)
 * Space: O(1)
 */
function jump(nums) {
    const n = nums.length;
    if (n <= 1) return 0;

    let jumps = 0;
    let pos = 0;

    while (pos < n - 1) {
        if (pos + nums[pos] >= n - 1) {
            jumps++;
            break;
        }

        let bestNext = pos + 1;
        let bestReach = 0;

        for (let i = pos + 1; i <= Math.min(pos + nums[pos], n - 1); i++) {
            if (i + nums[i] > bestReach) {
                bestReach = i + nums[i];
                bestNext = i;
            }
        }

        pos = bestNext;
        jumps++;
    }

    return jumps;
}

C#:

public class Solution {
    /// <summary>
    /// Find minimum jumps using forward-scanning greedy
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int Jump(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return 0;

        int jumps = 0;
        int pos = 0;

        while (pos < n - 1) {
            if (pos + nums[pos] >= n - 1) {
                jumps++;
                break;
            }

            int bestNext = pos + 1;
            int bestReach = 0;

            for (int i = pos + 1; i <= Math.Min(pos + nums[pos], n - 1); i++) {
                if (i + nums[i] > bestReach) {
                    bestReach = i + nums[i];
                    bestNext = i;
                }
            }

            pos = bestNext;
            jumps++;
        }

        return jumps;
    }
}

Key Insights

  1. BFS Analogy: Each jump corresponds to a BFS level. Positions reachable in 1 jump form level 1, positions reachable in 2 jumps form level 2, and so on. The first level that contains the last index gives the minimum jumps.

  2. Implicit BFS without Queue: By tracking currentEnd (boundary of current level) and farthest (boundary of next level), we simulate BFS without a queue, achieving O(1) space.

  3. Greedy Correctness: At each step, extending to the farthest reachable position is optimal because it maximizes future options. Any other choice can only do worse or equal.

  4. Loop Boundary: Iterating up to n - 2 (not n - 1) avoids counting an extra jump when we are already at or past the last index at the end of a level.

  5. Guaranteed Reachability: The problem guarantees a solution exists, so we never need to handle the case where the last index is unreachable.

Edge Cases

  • Single element: [0] → 0 (already at the last index)
  • Two elements: [1,0] → 1 (one jump from index 0 to index 1)
  • Direct reach: [10,1,1,1,1] → 1 (first element can jump past the end)
  • All ones: [1,1,1,1] → 3 (must jump one step at a time)
  • Large first, small rest: [5,1,1,1,1,1] → 1
  • Zigzag values: [2,1,3,1,1] → 2

Test Cases

# Test case 1: Standard case
assert jump([2,3,1,1,4]) == 2

# Test case 2: With zeros
assert jump([2,3,0,1,4]) == 2

# Test case 3: All ones
assert jump([1,1,1,1]) == 3

# Test case 4: Single element
assert jump([0]) == 0

# Test case 5: Direct jump to end
assert jump([10,1,1,1,1]) == 1

# Test case 6: Two elements
assert jump([1,0]) == 1

# Test case 7: Optimal path not obvious
assert jump([1,2,3]) == 2

# Test case 8: Large jumps throughout
assert jump([5,4,3,2,1,1]) == 2

Common Mistakes

  1. Iterating to n - 1 instead of n - 2: In the BFS approach, iterating to the last index can add an unnecessary jump when currentEnd already covers the last index.

  2. Not handling single element arrays: An array of length 1 needs 0 jumps since you start at the last index.

  3. Confusing Jump Game I with Jump Game II: Jump Game I asks if you can reach the end (boolean), while Jump Game II asks for the minimum number of jumps (integer). The greedy structure is similar but the tracking differs.

  4. Greedy scanning past array bounds: When scanning reachable positions, forgetting to cap the range at n - 1 causes index-out-of-bounds errors.

  5. Not breaking early: When farthest or currentEnd already exceeds n - 1, failing to break out of the loop may count extra iterations (though it typically does not change the answer in the BFS approach).