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:

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

Leave a Reply

Your email address will not be published.