Jump Game (opens in a new tab) Medium

Problem

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

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

Output: true

Summary

To solve this problem, we can iterate through the array and maintain a variable maxReach that stores the maximum index we can reach so far. If we reach an index greater than maxReach, it means we can't move forward, and we return false. If we reach the last index or beyond, we return true, indicating we can reach the last index.

Solution

In TypeScript

function canJump(nums: number[]): boolean {
    let maxReach = 0;
 
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) return true;
    }
 
    return false;
}

In Python

def canJump(nums: List[int]) -> bool:
		maxReach = 0
 
		for i in range(len(nums)):
				if i > maxReach: return False
				maxReach = max(maxReach, i + nums[i])
				if maxReach >= len(nums) - 1: return True
 
		return False

Step-by-step explanation

1. Initialize a variable called maxReach and set it to 0. This variable will be used to keep track of the maximum index we can reach so far while iterating through the array.

let maxReach = 0;

2. Iterate through the nums array using a for loop with an index variable i.

for (let i = 0; i < nums.length; i++) {
    // ...
}

3. Inside the for loop, check if the current index i is greater than maxReach. If it is, it means we can't move forward and reach the last index, so we return false.

if (i > maxReach) return false;

4. Update the maxReach variable by taking the maximum of the current maxReach value and the sum of the current index i and the value at the current index nums[i].

maxReach = Math.max(maxReach, i + nums[i]);

5. Check if maxReach is greater than or equal to the last index of the array (nums.length - 1). If it is, it means we can reach the last index, so we return true.

if (maxReach >= nums.length - 1) return true;

6. If the for loop completes without returning, we return false. This means we were unable to reach the last index of the array.

In summary, the canJump function iterates through the input array while maintaining a variable maxReach to keep track of the maximum index we can reach so far. If we reach an index greater than maxReach, we know we can't reach the last index and return false. If we reach the last index or beyond, we return true.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array. We iterate through the entire array once.

Space Complexity

The space complexity of this solution is O(1) since we only use a constant amount of additional space to store the maxReach variable.