Link to Question

MEDIUM

Jump Game II

You are given a 0-indexed array of integers nums of length n. Your goal is to reach the last index in the minimum number of jumps.

You can jump from index i to index i + x where 1 <= x <= nums[i].

Return the minimum number of jumps to reach the last index. The test cases are generated such that you can always reach the last index.

Example

Input:

nums = [2,3,1,1,4]

Output:

2

Explanation:
Jump from index 0 to 1, then from 1 to 4.

---

Constraints

• 1 ≤ nums.length ≤ 10⁴
• 0 ≤ nums[i] ≤ 1000

---

Solution: Greedy

• Time Complexity: O(n)
• Space Complexity: O(1)

C++

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