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

:::spoiler Hint

class Solution {
public:
    int jump(vector<int>& nums)
    {
        // This will store the farthest index we can reach so far
        // This will count the number of jumps needed
        // This will store the current goal index we aim to reach with the next jump
        
        // Loop through the array up to the second-to-last element
        for ()
        {
            // Update maxReach with the farthest we can reach from the current index
            
            // If we have reached the current goal
                // Increment the jump count
                // Update the goal to the farthest we can reach
            }
        }
        // Return the number of jumps needed to reach the last index
    }
};

:::

:::spoiler Solution

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

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