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]
andi + 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
Solution 1 :
class Solution {
public:
int jump(vector<int>& nums) {
int goal = nums.size() - 1;
int maxReach = 0, lastJump = 0, totalJump = 0;
// Base case
if (nums.size() == 1) return 0;
for (int i = 0; i < nums.size(); i++) {
maxReach = max(maxReach, i + nums[i]);
if (i == lastJump) {
lastJump = maxReach;
totalJump++;
if (maxReach >= goal) {
return totalJump;
}
}
}
return totalJump;
}
};
Solution 2 :
class Solution {
public:
int jump(vector<int>& nums) {
// Approach 2
int farthest;
int l = 0, r = 0, jump = 0;
if(nums.size() == 1) return 0;
while(r < nums.size()-1) {
farthest = 0;
for(int i = l; i <= r; i++) {
farthest = max(farthest, i + nums[i]);
}
l = r + 1;
r = farthest;
jump++;
}
return jump;
}
};