Problem statement

https://leetcode.com/problems/jump-game-ii/

Solution

There are two algorithms: one is dp with complexity O(n^2), where dp(i) is the minimum number of steps to reach position i and on each step we need to check potentially O(n) jumps.

However there is a solution with better complexity, using greedy idea: we need to look at i + nums[i] values and look at running maximum of these values. Then all we need to do is to start from the zero index and do ind = t[ind] until we reach the ending point or bigger.

We can look at our process like this: what is the biggest index we can reach after say i jumps. Then if we have new index to traverse we update our range. For example for nums = [2, 3, 0, 1, 4] we have t = [2, 4, 4, 4, 8] and after 1 jump we can reach index 2 and after each new index processed we expand our window if we have bigger value than the end of window and increase total number of steps or we do not do anything.

Complexity

Time complexity is O(n), space is O(n) as well, it can be made O(1), if we calculate cumulative maximum on the fly.

Code

class Solution:
    def jump(self, nums):
        t = list(accumulate([i + num for i, num in enumerate(nums)], max))
        ind, q = 0, 0
        while ind < len(nums) - 1:
            ind = t[ind]
            q += 1
        return q