Leetcode 45: Jump Game II

Only a linear solution will pass the leetcode tests. Use a three counters as we iterate: jumps, current steps left, next steps left. We only use next jump when we run out of current steps left. Continually update next steps left if the current position has > next steps left. I tried various other ways but they all timed out. Recursive is most obvious. Then recursive with DP memo. Then iterative DP O(n^2). Finally linear.

Source code for recursive+memo solution (too slow for leetcode test cases):
Iterative DP solution (also too slow for leetcode test cases):
And here’s the linear solution that passes the leetcode test cases:

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

Leave a Reply

Your email address will not be published.