Jump game II

You are given a 0-indexed integer array, `nums`, of length `n`. You start at index `0`. Each element `nums[i]` tells you the **maximum length** of a forward jump from index `i`. In other words, if you're at index `i`, you can jump to any index `i + j`, as long as:

Jump Game II

Problem Statement

You are given a 0-indexed integer array, nums, of length n. You start at index 0.

Each element nums[i] tells you the maximum length of a forward jump from index i. In other words, if you're at index i, you can jump to any index i + j, as long as:

• 0 ≤ j ≤ nums[i], and
• i + j < n

Return the minimum number of jumps needed to reach the last index, n - 1. The test cases are set up so that reaching the last index is always possible.

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 index 1, then jump 3 steps to reach the last index.

Example 2

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

Output: 2

Constraints

• 1 ≤ nums.length ≤ 10⁴
• 0 ≤ nums[i] ≤ 1000
• It's guaranteed that you can reach nums[n - 1].

Solution

This solution uses a greedy approach, thinking of the journey in terms of jump ranges rather than jumping one step at a time.

The Idea

• At any point, we know the farthest index we could possibly reach using our current jump.
• We also track the farthest index we could reach using one more jump, by checking every position within our current range.
• Once we reach the edge of what our current jump could cover, we know it's time to "use" that jump, and move our range forward to the new farthest point we found.

Steps

• We track three things:
  • jump: the number of jumps made so far.
  • farthest: the farthest index reachable using one more jump, based on everything we've seen so far.
  • currentEnd: the farthest index reachable using our jumps so far (before adding a new one).
• We go through the array, from index 0 up to (but not including) the last index:
  • At each index i, we update farthest to be the largest value between itself and i + nums[i] — this checks if jumping from here could get us farther than anything we've seen before.
  • If we've reached currentEnd (the edge of our current jump's range), it means we must use another jump to keep moving forward. So we increase jump by 1, and update currentEnd to farthest, extending our reachable range.
• By the end of the loop, jump holds the minimum number of jumps needed to reach the last index.

Code

var jump = function(nums) {

  let jump = 0;
  let farthest = 0;
  let currentEnd = 0;

  for (let i = 0; i < nums.length - 1; i++) {

    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {
        jump++;
        currentEnd = farthest;
    }
  }
  return jump;
};