Find minimum jumps to reach last index.
Input: nums=[2,3,1,1,4] → Output: 2
Input: nums=[2,3,0,1,4] → Output: 2
BFS greedy: track current range end and farthest reach.
- jumps=0, curEnd=0, farthest=0
- For i from 0 to n-2: farthest = max(farthest, i+nums[i])
- At i == curEnd: jumps++, curEnd=farthest
- Return jumps
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)