Leetcode 0055 Jump Game

Problem statement

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

Solution

Similar to problem 0045 Jump Game II, but here we need to check if we can reach the end. As in problem 0045 we can create cumulative maximum of i + nums[i] and check if for some element we have i == t[i]: if we have such place, we stuck and we can not reach the last cell, if not, we can reach.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def canJump(self, nums):
        t = list(accumulate([i + num for i, num in enumerate(nums)], max))
        return all(i != t[i] for i in range(len(t) - 1))