Jump Game medium

Problem Statement

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1

nums = [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2

nums = [3,2,1,0,4]

Output: false

Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Steps

The key idea is to track the furthest reachable index using a greedy approach. We iterate through the array, and for each index, we update the furthest reachable index. If the furthest reachable index ever reaches or exceeds the last index, we know we can reach the end. Otherwise, if we reach an index where the furthest reachable index is less than the current index, it means we can't reach the end.

Explanation

1. Initialization: We start with furthest set to 0, representing the furthest index we can reach initially.

2. Iteration: We iterate through the nums array.

3. Update furthest: For each index i, we calculate the maximum reachable index from that position: i + nums[i]. We update furthest to be the maximum of the current furthest and the newly calculated reachable index.

4. Check Reachability: After each iteration, we check if furthest is greater than or equal to the last index of the array. If it is, we can reach the end, so we return True.

5. Unreachable: If we complete the iteration and furthest is still less than the last index, it means we cannot reach the end, so we return False.

Code

def canJump(nums):
    """
    Determines if it's possible to reach the last index of an array given jump lengths.

    Args:
        nums: A list of non-negative integers representing maximum jump lengths.

    Returns:
        True if the last index is reachable, False otherwise.
    """
    n = len(nums)
    furthest = 0  # Furthest reachable index

    for i in range(n):
        furthest = max(furthest, i + nums[i])  # Update furthest reachable index
        if furthest >= n - 1:  # Check if last index is reachable
            return True
        if furthest <= i: #If we cannot reach beyond the current index, it is impossible to reach the end.
            return False

    return False  # Last index is not reachable

Complexity

• Time Complexity: O(n), where n is the length of the nums array. We iterate through the array once.
• Space Complexity: O(1). We use only a few constant extra variables.