55. Jump Game

Hint

class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        // Initialize goal as the last index of the array

        // Iterate backwards from the second last element to the first element
        for ()
        {
            // Check if the current index can reach the goal or beyond
            if ()
            {
                // Update the goal to the current index
            }
        }
        // If the goal is 0, it means the start index can reach the end
    }
};

• From right to left

class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        int goal = nums.size() - 1;
        for (int i = nums.size() - 1; i >= 0; --i)
        {
            if (nums[i] + i >= goal)
            {
                goal = i;
            }
        }
        return goal == 0;
    }
};

• T: $O(N)$

• S: $O(1)$

• From left to right

class Solution {
public:
    bool canJump(vector<int>& nums)
    {
        int n = nums.size();
        int maxReach = 0;
        for (int i = 0; i < n; ++i)
        {
            if (i > maxReach) return false;
            maxReach = max(maxReach, nums[i] + i);
        }
        return maxReach >= n - 1;
    }
};

• T: $O(N)$
• S: $O(1)$