Jump Game II

Problem Description

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 reach nums[n - 1].

Examples

Constraints

• 1 ≤ nums.length ≤ 10⁴
• 0 ≤ nums[i] ≤ 1000
• It’s guaranteed that you can reach the last index.

Greedy BFS Simulation

Think of this as a level-by-level BFS, where each level is the range of indices reachable within a certain number of jumps:

• Level 0: [0, 0] (0 jumps).
• Level 1: indices reachable from level 0 (from index 0, we can jump to any index up to nums[0]).
• Level 2: indices reachable from level 1.

We maintain:

• currentEnd: the farthest boundary of the current jump level.
• farthest: the farthest index we can reach from any index in the current level.
• jumps: the count of jumps (levels).

Iterate through the array up to n - 2. Update farthest = max(farthest, i + nums[i]). When we reach currentEnd, we must make another jump: increment jumps and update currentEnd = farthest. If currentEnd already reaches or exceeds n - 1, we can stop early.

Solution: Greedy Range Extension

class Solution {
    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]);

            // when we reach the end of the current jump range
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;

                if (currentEnd >= n - 1) break; // early exit
            }
        }

        return jumps;
    }
}

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
                
                if current_end >= n - 1:
                    break

        return jumps

#include <vector>
#include <algorithm>

class Solution {
public:
    int jump(std::vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 0;

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

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

            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                if (currentEnd >= n - 1) break;
            }
        }

        return jumps;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of nums. We scan the array once.
• Space Complexity: O(1) space.

← All Problems