Leetcode problem 76 - Rotate Array

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].

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
  // Initialize variables
  let jump = 0; // The furthest position that can be reached
  let far = 0; // The furthest position reached so far
  let output = 0; // Number of jumps needed

  // Iterate through the array
  for (let i = 0; i < nums.length - 1; i++) {
    // Update the furthest position that can be reached
    jump = Math.max(jump, i + nums[i]);

    // If the current position is equal to the furthest position reached so far
    if (i == far) {
      far = jump; // Update the furthest position reached so far
      output++; // Increment the number of jumps needed
    }
  }

  return output; // Return the minimum number of jumps
};

The jump variable keeps track of the furthest position that can be reached from the current position.

The loop iterates through the array, updating the jump variable to store the maximum value between its current value and the sum of the current index and the number of positions that can be jumped from that index.

If the current index is equal to the furthest position reached so far (far), it means that a jump is needed to move forward, so update far to the latest value of jump and increment the output variable (the number of jumps needed).

Repeat these steps until you reach the last index of the array.

Return the minimum number of jumps needed to reach the last index.

The time complexity of this algorithm is O(n), where n is the length of the input array nums. The reason for this linear time complexity is that the algorithm iterates through the array exactly once in a single loop.