[Programming Problem] Jump Game II

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.

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

[Programming Problem]

At every step jump and update values (if smaller) in the landing step. Let’s take the example of [2, 3, 1, 1, 4]. We start by initializing the ret array with MAX_VALUE’s. Then for position 0, we update position 1 and 2 with updated minimum value of 1. We keep doing this for the full array.

[2, 3, 1, 1, 4]
 
Initialize           -> [ 0, 1.797e+308, 1.797e+308, 1.797e+308, 1.797e+308 ]
Jump from position 0 -> [ 0, 1, 1, 1.797e+308, 1.797e+308 ]
Jump from position 1 -> [ 0, 1, 1, 2, 2 ]
Jump from position 2 -> [ 0, 1, 1, 2, 2 ]
Jump from position 3 -> [ 0, 1, 1, 2, 2 ]
Jump from position 4 -> [ 0, 1, 1, 2, 2 ]
[3, 0, 0, 1, 4]
 
Initialize           -> [ 0, 1.797e+308, 1.797e+308, 1.797e+308, 1.797e+308 ]
Jump from position 0 -> [ 0, 1, 1, 1, 1.797e+308 ]
Jump from position 1 -> [ 0, 1, 1, 1, 1.797e+308 ]
Jump from position 2 -> [ 0, 1, 1, 1, 1.797e+308 ]
Jump from position 3 -> [ 0, 1, 1, 1, 2 ]
Jump from position 4 -> [ 0, 1, 1, 1, 2 ]
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    const ret = [0].concat(new Array(nums.length-1).fill(Number.MAX_VALUE));
    for (let i = 0 ; i < nums.length ; i++ ) {
        let currStep = nums[i];
        //console.log(i, currStep)
        for (let jump = 1 ; jump <= currStep ; jump++) {
            //console.log("jump", jump, i + jump)
            if ( ret[i + jump] > ret[i] + 1 ) {
                ret[i + jump] = ret[i] + 1
            }
        }
    }
    //console.log(ret)
    return ret[nums.length-1]
};

6 thoughts on “[Programming Problem] Jump Game II

  1. I must point out my admiration for your kindness supporting visitors who absolutely need help with this content. Your very own commitment to passing the message all through came to be rather beneficial and have consistently enabled ladies like me to achieve their endeavors. This informative recommendations signifies a great deal to me and extremely more to my office colleagues. Many thanks; from everyone of us.

  2. I want to express my affection for your kind-heartedness for persons who really want guidance on in this niche. Your real dedication to getting the message across has been really beneficial and have regularly empowered guys like me to arrive at their desired goals. The informative help and advice signifies a lot a person like me and somewhat more to my office colleagues. Regards; from each one of us.

  3. I have to get across my respect for your kind-heartedness supporting all those that really want help with this important area. Your very own dedication to passing the solution all through appears to be certainly functional and has continually permitted those just like me to realize their desired goals. Your entire interesting publication denotes much to me and especially to my peers. Many thanks; from all of us.

  4. I want to voice my love for your kind-heartedness supporting visitors who need help with this issue. Your personal dedication to getting the solution all around was quite functional and has regularly encouraged associates like me to realize their targets. Your new invaluable guideline means a great deal a person like me and additionally to my office workers. Thank you; from everyone of us.

  5. I want to convey my admiration for your kind-heartedness in support of those people who must have guidance on in this issue. Your personal dedication to getting the message throughout ended up being definitely powerful and have constantly enabled those like me to reach their dreams. Your new invaluable information indicates a whole lot to me and especially to my mates. Thanks a ton; from everyone of us.

Leave a Reply

Your email address will not be published.