You’ve been provided with the nums integer array, representing the series of squares. You’re initially positioned at the first index of the array. Find the minimum number of jumps needed to reach the last index of the array. You may assume that you can always reach the last index.

jump-game.js

export function jumpGameTwo(nums) {
  if (nums.length === 1) {
    return 0;
  }

  // our current position in the array
  let current = 0;
  // the farthest index that is reachable from elements iterated up until now
  let farthest = 0;
  // number of jumps done
  let jumps = 0;

  for (let i = 0; i < nums.length; ++i) {
    // index that is reachable from position i is the value in nums[i] plus i itself
    // we are tracking the maximum (farthest) index found so far
    farthest = Math.max(farthest, i + nums[i]);
    // if our iteration reached our position in the array, we need to make a jump
    if (i === current) {
      current = farthest;
      jumps += 1;
      if (farthest === nums.length - 1) {
        // we have reached the last element in the array
        break;
      }
    }
  }

  return jumps;
}

// O(n), mem O(1).