Jump Game II

How it works

This problem asks for the minimum number of jumps needed to reach the last index.

We can think of this problem as moving level by level, similar to Breadth First Search (BFS):

• each “level” represents all positions we can reach using the same number of jumps
• from those positions, we compute how far we can reach in one more jump

Instead of explicitly using a queue, we use a greedy window:

• [l, r] represents the range of indices reachable with the current number of jumps
• from this range, we find the farthest index we can reach in the next jump

Once we finish scanning the current range, we move to the next range and increase the jump count.

Steps

1. Initialize:
   • res = 0 to count the number of jumps
   • l = 0, r = 0 to represent the current reachable range
2. While the right boundary r has not reached the last index:
3. For all indices i in the current range [l, r]:
   • Compute the farthest index reachable using one more jump: farthest = max(i + nums[i])
4. After scanning the range:
   • Update the next range: l = r + 1, r = farthest
   • Increment the jump count res
5. Repeat until the last index is included in the range
6. Return res

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Greedily Jumping to the Maximum Each Time

A common mistake is to always jump to i + nums[i] (the farthest reachable position). This greedy choice does not guarantee the minimum number of jumps. Instead, you should consider all positions reachable from the current range and pick the one that maximizes your reach for the next jump.

Off-by-One Errors in Range Boundaries

When implementing the BFS-style greedy solution, the window [l, r] represents the current level of reachable positions. Incorrectly updating l or r after processing a level can cause positions to be skipped or processed multiple times, leading to wrong jump counts.

Handling Zero-Value Elements

If nums[i] == 0, you cannot make progress from position i. In recursive or DP solutions, this should return infinity (or a large value) to indicate an invalid path. Forgetting this check can cause incorrect results when a path leads to a dead end.

from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        res = 0
        l = r = 0

        while r < len(nums) - 1:
            farthest = 0
            for i in range(l, r + 1):
                farthest = max(farthest, i + nums[i])
            l = r + 1
            r = farthest
            res += 1
        return res

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, l = 0, r = 0;

        while (r < nums.size() - 1) {
            int farthest = 0;
            for (int i = l; i <= r; i++) {
                farthest = max(farthest, i + nums[i]);
            }
            l = r + 1;
            r = farthest;
            res++;
        }
        return res;
    }
};