45. Jump Game II

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

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

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