45. Jump Game II

Jump Game II

Problem Description

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

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

Approach) Greedy 

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    const max_jump = new Array(nums.length);
    let max = nums[0];
    for (let i = 0; i<nums.length; i++) {
        max = Math.max(max, nums[i] + i);
        max_jump[i] = max;
    }
    let i = 0;
    let count = 0;
    while (i < nums.length - 1) {
        i = max_jump[i];
        count++;
    }
    return count;
};

Approach) Tabulation - (DP) Dynamic Programming

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let n = nums.length
    const dp = Array(n)
    dp[0] = 0
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (j + nums[j] >= i) {
                dp[i] = dp[j] + 1
                break
            }
        }
    }
    
    return dp[n-1]
};

Approach) BFS (Breadth First Search)

var jump = function(nums) {
    if(!nums.length) return;
    if(nums.length==1) return 0;
    let queue = [];
    let obj = {
        val: nums[0],
        idx: 0,
        count:0
    };
    let visited = Array(nums.length).fill(0);
    queue.push({...obj});
    while(queue.length) {
        var tmp = {...queue[0]};
        for(var i=tmp.val; i>=1; i--) {
            if(visited[tmp.idx+i]) continue;
            if(tmp.idx+i >= nums.length-1) return tmp.count+1;
            if(tmp.idx+i + nums[tmp.idx+i] >= nums.length-1) return tmp.count+2;
            obj.idx= tmp.idx+i;
            obj.val= nums[tmp.idx+i];
            obj.count= tmp.count+1;
            queue.push({...obj});
            visited[tmp.idx+i]=1;
        }        
        queue.shift();
    }
};

Approach) (DP) Dynamic Programming

The idea I had was like a car having a gas, where we can "refuel" with values we find along the way. It's basically a worse version of this. The key difference between this and the linked solution is that I didn't think to base the added distance off the index of the item plus the amount it can add.
Further, I didn't realize we know exactly when we need to jump, so you don't need to be guessing when you are out of gas. The speed between the two is the same, but the linked solution is a bit cleaner.

var jump2 = function(nums) {
    if (nums.length < 2) return 0
    let gas = 0, gasAvailable = 0, jumps = 0
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] > gasAvailable) gasAvailable = nums[i]
        if (gas == 0) {
            gas = gasAvailable
            jumps++
        }
        gas--
        gasAvailable--
    }
    return jumps
};

It's similar to the one above, but the key difference is that you are calculating the next jump in one slice, rather than constantly updating it as you go. This solution works like a caterpillar, the other works more like a bowling ball.

var jump3 = function(nums) {
    if (nums.length < 2) return 0
    let left = 0, right = nums[0], jumps = 1
    while (right < nums.length - 1) {
        jumps++
        let nextIndex = -1
        for (let i = left; i < right + 1; i++) {
            if (i + nums[i] > nextIndex) nextIndex = i + nums[i]
        }
        left = right
        right = nextIndex
    }
    return jumps
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem 45. Jump Game II

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!