Jump Game

Solution

Let $n$ be the length of the array nums.

Greedy Algorithm

Complexity

time: $O(n)$
space: $O(1)$

def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    max_pos = 0
    for i, jump in enumerate(nums):
        if i > max_pos: # current index is beyond reach
            return False
        if i + jump > max_pos: # update furthest reached point
            max_pos = i + jump
        if max_pos >= n-1: # can reach last position
            return True
    return False