[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
    return ret[nums.length-1]

11 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.

  6. I intended to compose you a little bit of note in order to thank you so much once again with the stunning thoughts you’ve contributed in this case. This has been so incredibly open-handed with people like you to grant publicly just what a number of us would’ve marketed for an ebook in order to make some cash for their own end, principally considering the fact that you could have done it if you decided. Those tips in addition acted to be the easy way to fully grasp most people have similar dreams like my personal own to know the truth way more around this issue. I am sure there are lots of more fun opportunities up front for many who check out your website.

  7. Thanks so much for providing individuals with remarkably breathtaking chance to check tips from here. It is always very nice plus full of a good time for me personally and my office fellow workers to visit the blog a minimum of thrice in 7 days to read through the fresh issues you have. And of course, we’re usually amazed with your astounding knowledge you give. Selected 2 ideas in this posting are easily the most impressive we’ve ever had.

  8. I precisely wished to say thanks once more. I am not sure the things I could possibly have taken care of in the absence of these thoughts provided by you over such a topic. It was actually a real terrifying dilemma in my view, but finding out the expert fashion you resolved the issue took me to jump with gladness. Extremely happier for your service and then sincerely hope you find out what an amazing job your are carrying out teaching other individuals by way of your site. Most probably you have never come across any of us.

  9. I precisely desired to appreciate you once again. I’m not certain the things that I could possibly have undertaken without the aspects revealed by you relating to such a subject. It previously was the scary situation in my circumstances, however , encountering your well-written way you processed that took me to cry with contentment. I will be grateful for the support and pray you comprehend what an amazing job you have been doing teaching the others via your websites. More than likely you’ve never come across any of us.

  10. Needed to write you one very small word to finally give many thanks once again for your splendid techniques you’ve documented on this page. It was simply strangely open-handed of you to make publicly all that many individuals would have offered for sale for an ebook to generate some dough for their own end, specifically seeing that you might well have done it in the event you desired. Those smart ideas as well served to be a easy way to recognize that other people online have the same fervor much like mine to learn way more in respect of this condition. Certainly there are some more fun occasions ahead for many who see your website.

Leave a Reply

Your email address will not be published. Required fields are marked *