Problem
You are given an integer arraynums, where nums[i] represents the maximum number of positions you can jump forward from index i.
You start at index
0. Return the minimum number of jumps required to reach the last index. You can assume that the last index is always reachable.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [2,3,1,1,4]Output
2Solution
This solution uses the Greedy pattern. We maintain two boundaries: maxReach and currentReach.The key idea is we don't decide the next jump immediately. We keep exploring all positions reachable within the current jump.
currentReach represents the boundary of the current jump. We keep moving through all indices within this boundary. While doing that, we calculate maxReach, which is the farthest position we could reach by taking the next jump from any of those indices.
When we reach currentReach, the current jump is exhausted. We must take another jump, so we increment
jump and make maxReach the new currentReach.
In other words, we choose the next jump that takes us farthest among all possibilities discovered during the current jump.
class Solution {
public int jump(int[] nums) {
int jump = 0;
int maxReach = 0;
int currentReach = 0;
// Loop stops at n - 1 because we don't need to jump from the last index
for (int i = 0; i < nums.length - 1; i++) {
// Update the farthest index reachable so far.
maxReach = Math.max(maxReach, i + nums[i]);
// Current jump boundary is reached.
if (i == currentReach) {
jump++;
// Extend the boundary using the farthest reach found.
currentReach = maxReach;
}
}
return jump;
}
}Complexity
We traverse the array once, so the time complexity isO(n), where n is the length of the array. The solution uses only a few variables, so the extra space complexity is O(1).