55. Jump Game

Jump Game - LeetCodeLeetCode

time: O(n) why? cuz I mark true once

space: O(n)

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if (nums.length === 1) return true;

    const visit = new Array(nums.length).fill(false);
    visit[0] = true;

    for (let i = 0; i < nums.length - 1; i++) {
        if (visit[i] === false) continue;
        if (i + nums[i] >= nums.length - 1) 
            return true;
        for (let j = i + nums[i]; j > 0; j--) {
            const flag = visit[j];
            if (flag) break;
            visit[j] = true;
        }
    }

    return false;
};