Jump Game II

Minimum Number of jums required to reach end

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.

At Every Index we see how far we can go. For zeroth index we only have one option so we mark far as whatever value is provided and mark it as currentEnd and increment value of jump. now between the journey of current index and currentEnd we calculate what's the biggest value we have seen that once we reach current end we make decision to mark the farthest value as our new currentEnd and take another jump

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;
};