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):
https://gist.github.com/adamkorg/4cd63f9cf0045ed58c9d9fd20712ef46
Iterative DP solution (also too slow for leetcode test cases):
https://gist.github.com/adamkorg/6bbd0487c0e29ec1d824d156e400cfc7
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.