LeetCode 45. Jump Game II (javascript solution)

#algorithms #javascript

Description:

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Solution:

Time Complexity : O(n)
Space Complexity: O(1)

 // Greedy solution
var jump = function(nums) {
    let newMax = 0;
    let jump = 0;
    let oldMax = 0;
    for (let i=0;i<nums.length-1;i++) {
        // Keep track of the farthest jump
        newMax = Math.max(newMax, i+nums[i]);
        // When we get to the index where we had our previous farthest jump, we increase our jump count by 1
        if (i == oldMax) {
            jump++;
            oldMax = newMax;
        }
    }
    return jump;
};