0045. Jump Game II.md

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.

C++

class Solution {
public:
    int jump(vector<int>& nums) {
        int currStep = 0, maxStep = 0, count = 0;
        for(int i = 0; i < nums.size() - 1; i++) {
            maxStep = max(maxStep, i + nums[i]);
            if(i == currStep) {
                currStep = maxStep;
                count++;
            }
        }
        return count;
    }
};

JS

/**
 * @param {number[]} nums
 * @return {number}
 */

/*
every time i move forward to next index, which mean + 1
i will touch each single index, as long as we reach the currentJumpEnd, 
that means we should ready for next jump

Time complexityL O(n) because there are NN elements in the array 
and we visit each element in the array only once.

Space Complexity: O(1)because we don't use any additional data structures.
*/
var jump = function(nums) {
    let farthest = 0, curJumpEnd = 0, jump = 0;
    
    for(let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, nums[i] + i);
        if(i === curJumpEnd) {
            jump++;
            curJumpEnd = farthest;
        }
    }
    return jump;
};