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:

Input: 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:

Input: 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:

1. Initialization: Start with a reachable variable set to 0. This represents the furthest index we can reach so far.

2. Iteration: Iterate through the nums array.

3. Update Reachable: For each index i, update reachable to the maximum of reachable and i + nums[i]. This means we can reach at least as far as the current position plus the maximum jump from that position.

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

5. Failure: If the loop completes without reaching the end, it means it's impossible to reach the last index, so we return false.

Explanation:

The algorithm uses a greedy approach. At each step, we find the furthest point we can reach from the current position. If at any point the furthest reachable index is greater than or equal to the last index, we know we can reach the end. If we iterate through the entire array and never reach the end, it's impossible.

Code:

function canJump(nums: number[]): boolean {
    let reachable = 0; // Furthest index reachable so far

    for (let i = 0; i < nums.length; i++) {
        // Update reachable index
        reachable = Math.max(reachable, i + nums[i]);

        // Check if we can reach the end
        if (reachable >= nums.length - 1) {
            return true;
        }

        //If we can't reach the current index, we can't reach the end.
        if(i > reachable) return false;
    }

    return false; // Cannot reach the end
};

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 only use a constant amount of extra space.