Problem Statement in English

You’re given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Approach

We can do this greedily.

The idea is to keep track of the farthest index we can reach as we iterate through the array. If at any point, the farthest index we can reach is less than the current index, it means we cannot proceed further, and we return false.

If we can reach or exceed the last index, we return true.

And we’re done!

Solution in Python


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        farthest = 0
        
        for i in range(N):
            if farthest < i: return False
            farthest = max(farthest, i + nums[i])

        return True

Complexity

  • Time: $O(N)$
    Since we are iterating through the array once, the time complexity is linear with respect to the number of elements in nums.

  • Space: $O(1)$
    Since we are using a constant amount of extra space (only a few variables), the space complexity is constant.

And we are done.