Jump Game

Can a user jump and react to the end of array

Jump Game

Problem Statement

In this single-player game, the player starts at one end of a series of squares, with the goal of reaching the last square.

On each turn, the player can move up to s steps toward the last square, where s is the value of the current square.

For example, if the current square's value is 3, the player can move 3 steps, 2 steps, or 1 step toward the last square. The player cannot move in the opposite direction (away from the last square).

Your task is to write a function that checks whether the player can win a given game.

You're given an integer array, nums, representing the series of squares. The player starts at the first index, and following the rules above, tries to reach the last index.

Return TRUE if the player can reach the last index, or FALSE otherwise.

Constraints

• 1 ≤ nums.length ≤ 10³
• 0 ≤ nums[i] ≤ 10³

Note: This is essentially the same underlying problem as the classic "Jump Game" problem (checking if you can reach the last index using each value as your maximum forward jump length), just described using different wording ("squares" and "steps" instead of "array" and "jumps").

Solution

Instead of thinking about this problem moving forward from the start, it's easier to work backward from the end.

The Idea

• We start by assuming the last index is our current target — the spot we need to be able to reach.
• We 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 works because if this position can reach the old target, and the old target could reach the end, then reaching this position is now just as good as reaching the end.
• We repeat this all the way back to index 0.
• If, by the end, our target has been reduced all the way down to index 0, it means the very first square can eventually reach the last one. We return true. Otherwise, we return false.

Code

let jumpGame = 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;
};