Leetcode 55: Jump Game

The key insight to find the optimal O(n) solution is that we should evaluate our situation at every step as we iterate through the array, trying to maximise our remaining steps available. So in the first whiteboard example [2,3,1,1,4], we start at 2 so we have 2 steps available. We move on to the second element, so our remaining steps from the first element has gone down to one. Now we decide if we stop on this element and use its steps, which is 3, which is greater than our 1 step left, so we do. We now have 3 steps available. We continue like this until the last element.

Recursive with memoization solution timed out on leetcode test cases:
https://gist.github.com/adamkorg/f0e1ab8394dede0fd36ce6267e56bd96

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

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