Back to DSA
Jump Game II
hardStarting at the first element of an integer array, reach the last element using the minimum number of jumps. From index i you may jump forward by up to nums[i] positions. It is guaranteed that the last index is always reachable.
Examples
Example 1:
Input:
nums = [1,3,2,1,4]Output:
2 Example 2:
Input:
nums = [3,2,1,0,4]Output:
2Hints
class Solution {
public int jump(int[] nums) {
int jumps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == curEnd) { jumps++; curEnd = farthest; }
}
return jumps;
}
}Time complexity
O(n)Space complexity
O(1)