# [55\. Jump Game](https://leetcode.com/problems/jump-game/)

:::spoiler 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
    }
};

:::

:::spoiler Solution - 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;
    }
};

- 時間複雜度：$O(N)$
- 空間複雜度：$O(1)$
:::

:::spoiler Solution - 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;
    }
};

- 時間複雜度：$O(N)$
- 空間複雜度：$O(1)$
:::