55. Jump Game

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)$