Jump Game

You are given an integer array, nums. You start at the first index of the array. Each element in the array tells you your maximum jump length from that position.

Jump Game

Problem Statement

You are given an integer array, nums. You start at the first index of the array. Each element in the array tells you your maximum jump length from that position.

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

Examples

Example 1

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

Output: true

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

Example 2

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

Output: false

Explanation: No matter what you do, you will always end up at index 3. Its maximum jump length is 0, so it's impossible to move past it and reach the last index.

Constraints

• 1 ≤ nums.length ≤ 10⁴
• 0 ≤ nums[i] ≤ 10⁵

Solution

Instead of thinking about this problem forward (checking every possible jump from the start), it's easier to think about it backward.

The Idea

• We start by assuming the last index is our target — the spot we need to reach.
• We then walk backward through the array, one position at a time.
• At each position, we check: "Can I reach my current target from here?" This is true if position + nums[position] is greater than or equal to the target index.
• If we can reach the target from this position, this position now becomes our new target. This is because if we can reach the old target from here, and the old target could reach the end, then reaching this position is now just as good as reaching the end.
• We keep doing this all the way back to index 0.
• At the end, if our target has been reduced all the way down to index 0, it means the very first index can eventually reach the last index. So we return true. Otherwise, we return false.

Code

var canJump = function (nums) {
    let targetNumIndex = nums.length - 1;

    for (let i = nums.length - 2; i >= 0; i--) {
        if (targetNumIndex <= i + nums[i]) {
            targetNumIndex = i;
        }
    }

    if (targetNumIndex == 0) {
        return true;
    }

    return false;
};