[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]
};

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

  11. Thank you a lot for giving everyone an extraordinarily terrific possiblity to discover important secrets from here. It is usually so cool and stuffed with a lot of fun for me and my office friends to visit your website at least 3 times in one week to read through the latest guidance you have. Of course, I’m so usually contented for the effective tips served by you. Selected 4 areas on this page are in truth the most efficient we’ve had.

  12. I simply wanted to thank you so much yet again. I do not know the things that I would’ve undertaken without these methods discussed by you on this problem. It was before a very difficult condition in my opinion, but seeing a new specialized fashion you managed it took me to weep over delight. Now i am thankful for this service and as well , believe you recognize what a great job you’re carrying out instructing other individuals thru your site. Most likely you’ve never met any of us.

  13. I have to voice my respect for your kindness for people who really want assistance with your issue. Your personal dedication to getting the message throughout has been incredibly significant and has all the time allowed ladies much like me to arrive at their dreams. Your personal interesting tips and hints signifies a great deal to me and especially to my peers. Thank you; from everyone of us.

  14. Can I just say what a aid to find someone who actually knows what theyre talking about on the internet. You positively know methods to carry an issue to light and make it important. More folks have to read this and perceive this facet of the story. I cant imagine youre no more fashionable because you undoubtedly have the gift.

  15. I wish to convey my affection for your kind-heartedness for visitors who need assistance with this particular issue. Your very own commitment to passing the solution around ended up being wonderfully practical and have continually empowered most people much like me to attain their goals. The informative guide denotes a great deal a person like me and especially to my fellow workers. Many thanks; from everyone of us.

  16. I precisely wished to say thanks all over again. I am not sure the things that I would have made to happen without those ways shared by you regarding my theme. It became the intimidating case for me, however , spending time with a well-written fashion you resolved that made me to jump over delight. I’m thankful for your information and as well , hope that you know what a powerful job you are undertaking teaching many others via a site. More than likely you’ve never encountered any of us.

  17. My husband and i have been very fortunate Emmanuel could carry out his inquiry using the ideas he discovered through the weblog. It is now and again perplexing to just continually be freely giving procedures men and women may have been selling. And we also do understand we have you to appreciate for that. Most of the illustrations you’ve made, the easy web site navigation, the friendships you will give support to engender – it’s got many unbelievable, and it’s leading our son in addition to our family believe that that topic is brilliant, and that is extraordinarily essential. Thank you for everything!

  18. I would like to point out my affection for your generosity in support of folks that require help on this important study. Your personal commitment to getting the message around has been pretty powerful and have truly permitted men and women like me to arrive at their targets. Your personal helpful advice signifies a great deal a person like me and substantially more to my office workers. Regards; from each one of us.

  19. I have to show my appreciation for your kind-heartedness in support of men and women who really need guidance on this idea. Your personal dedication to getting the solution around came to be particularly insightful and have really helped folks like me to realize their ambitions. This warm and helpful useful information means a great deal to me and even further to my colleagues. Warm regards; from everyone of us.

  20. I wish to get across my appreciation for your kind-heartedness for people that should have guidance on that area of interest. Your special dedication to passing the message along had been quite powerful and have surely enabled somebody much like me to achieve their endeavors. Your new informative facts denotes so much a person like me and extremely more to my office workers. Thank you; from all of us.

  21. My wife and i got so ecstatic Edward could deal with his analysis with the ideas he was given from your site. It is now and again perplexing just to possibly be handing out techniques that many other folks might have been selling. So we grasp we have the blog owner to give thanks to because of that. The entire explanations you made, the easy website navigation, the friendships you will make it easier to create – it’s mostly amazing, and it is facilitating our son and the family believe that the content is exciting, which is certainly exceedingly vital. Many thanks for the whole thing!

  22. I must show my respect for your generosity supporting folks that need guidance on in this theme. Your very own commitment to getting the message all through came to be wonderfully valuable and has always empowered ladies much like me to get to their aims. Your entire insightful suggestions indicates a whole lot to me and even more to my mates. Regards; from each one of us.

  23. I want to show my affection for your kindness for individuals that should have help with this important field. Your very own commitment to getting the solution around ended up being pretty significant and has without exception empowered women like me to get to their desired goals. Your amazing insightful recommendations means so much a person like me and a whole lot more to my office colleagues. Thanks a lot; from each one of us.

  24. I simply wanted to thank you so much once again. I do not know the things that I could possibly have carried out in the absence of the actual techniques documented by you relating to such theme. It had been the traumatic issue in my position, however , observing the well-written manner you treated it took me to leap over gladness. I am happier for your work and as well , hope that you comprehend what a powerful job you are putting in instructing the mediocre ones with the aid of a web site. Most probably you haven’t met all of us.

  25. 564748 218392This douche bag loves his illegal bretheren because hes a itiaen with the world and we really should be ashamed of ourselves I got news for you Asswipe get your asswiping ass back to the craphole exactly where you came from with all of your illegal beaners 447507

  26. My spouse and i ended up being quite peaceful when Chris could do his inquiry because of the ideas he was given from your own web pages. It’s not at all simplistic to simply choose to be handing out tips and tricks which many people have been selling. And we all do understand we have the blog owner to give thanks to for this. The most important illustrations you made, the easy blog navigation, the friendships you can assist to foster – it’s everything sensational, and it’s letting our son in addition to our family consider that this subject matter is entertaining, and that is rather important. Many thanks for all!

  27. Needed to post you one little remark to help say thanks a lot the moment again over the pleasing views you have discussed in this case. This has been so strangely generous of you to grant easily all that many of us would’ve offered as an e-book to help with making some profit for themselves, certainly since you might have done it if you ever wanted. These smart ideas also served to become great way to be certain that most people have the identical passion like my very own to realize many more with reference to this condition. I’m sure there are a lot more pleasurable opportunities ahead for individuals that go through your website.

  28. I wish to show my respect for your kind-heartedness for those people that actually need help with that area of interest. Your real commitment to passing the message up and down ended up being really invaluable and has specifically allowed individuals much like me to achieve their pursuits. This warm and friendly help signifies a lot to me and substantially more to my colleagues. Thanks a ton; from all of us.

Leave a Reply

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