Medium

Jump Game

069

Return true if you can reach the last index when nums[i] is the maximum jump length from i.

EXAMPLES

Example 1

Input
{
  "nums": [
    2,
    3,
    1,
    1,
    4
  ]
}

Output
true

FUNCTION SHAPE

nums: intArray→bool

SOLUTION NOTE

The intuition is that starting at index 0, we extend our max range to the furthest possible index we can reach so far. Once we are at some index that is beyond our reach, we clearly cannot reach the end so we return false. Otherwise we return true.

Reveal reference solution +

pythonREFERENCE

# l->r greedy, keep track of max distance can reach so far
def canJump(self, nums: List[int]) -> bool:
    n, reach = len(nums), 0

    for i in range(n):
        if i > reach: return False
        reach = max(reach, i + nums[i])

    return True

TimeO(n)

SpaceO(1)

Open on LeetCode ↗