Jump Game

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

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

First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.

Approach

Greedily track the farthest index reachable so far. As you scan, if the current index exceeds the farthest reach, return false. Otherwise, update the farthest reach with i + nums[i].

Why It Works

If you can reach index i, then you can reach all indices up to the farthest reach computed. If you ever encounter an index beyond that, no sequence of jumps can reach it. If the scan finishes, the last index is reachable.

Complexity

• Time: O(n)
• Space: O(1)

Reference Implementation (Python)

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