Skip to content

Jump Game II⚓︎

Link

Description⚓︎

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

  • Input: nums = [2,3,1,1,4]
  • Output: 2
  • Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

  • Input: nums = [2,3,0,1,4]
  • Output: 2

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

Solution⚓︎

Greedy Solution 1⚓︎

1D BFS:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0;
        int start = 0, end = 0;
        while (end < nums.size() - 1) {
            int maxPosition = 0;
            for (int i = 0; i < end + 1; i++) {
                maxPosition = max(maxPosition, i + nums[i]);
            }
            start = end + 1;
            end = maxPosition;
            res += 1;
        }
        return res;
    }
};

Greedy Solution 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int jump(vector<int>& nums) {
        int currentBorder = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            maxPosition = max(maxPosition, nums[i] + i);
            if (i == currentBorder) {
                currentBorder = maxPosition;
                steps++;
            }
        }
        return steps;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).