Problem Statement:
You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:
0 <= j <= nums[i]andi + j < n
Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.
Examples:
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 <= 104
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Approach
Traversethe array while tracking the maximum index reachable from the current positions.- Use three variables:
farthest→ the farthest index that can be reached from the current range.currEnd→ the end of the current jump range.jumps→ number of jumps taken.
- For each
index i, update the farthest reachable position using farthest = Math.max(farthest, i + nums[i]). -
When i reaches
currEnd, it means the current jump range is exhausted, so:- Increase
currEnd. - Update currEnd to farthest to start the
next jump range.
- Increase
- Continue this process until the second last index, since the last index does not require another jump.
Dry Run
Input: nums = [2, 3, 1, 1, 4]
Initialization: currEnd = 0 farthest = 0 jumps = 0 Step 1: i = 0 Update farthest: farthest = max(0, 0 + nums[0]) farthest = max(0, 2) farthest = 2 Check: i == currEnd ? 0 == 0 → true Take a jump jumps = 1 currEnd = farthest = 2 Step 2: i = 1 Update farthest: farthest = max(2, 1 + nums[1]) farthest = max(2, 4) farthest = 4 Check: i == currEnd ? 1 == 2 → false No jump taken Step 3: i = 2 Update farthest: farthest = max(4, 2 + nums[2]) farthest = max(4, 3) farthest = 4 Check: i == currEnd ? 2 == 2 → true Take a jump jumps = 2 currEnd = farthest = 4 Loop stops at i = nums.length - 2 (i = 3 was not needed to extend range further) Current range already reaches the last index.
Output: 2
var jump = function(nums) {
let currEnd = farthest = jumps = 0;
for(let i=0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if(i == currEnd) {
currEnd = farthest;
jumps++;
}
}
return jumps;
};
def jump(nums):
currEnd = 0
farthest = 0
jumps = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == currEnd:
currEnd = farthest
jumps += 1
return jumps
class Solution {
public int jump(int[] nums) {
int currEnd = 0;
int farthest = 0;
int jumps = 0;
for(int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if(i == currEnd) {
currEnd = farthest;
jumps++;
}
}
return jumps;
}
}
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int jump(vector& nums) {
int currEnd = 0;
int farthest = 0;
int jumps = 0;
for(int i = 0; i < nums.size() - 1; i++) {
farthest = max(farthest, i + nums[i]);
if(i == currEnd) {
currEnd = farthest;
jumps++;
}
}
return jumps;
}
};
int jump(int* nums, int numsSize) {
int currEnd = 0;
int farthest = 0;
int jumps = 0;
for(int i = 0; i < numsSize - 1; i++) {
if(farthest < i + nums[i])
farthest = i + nums[i];
if(i == currEnd) {
currEnd = farthest;
jumps++;
}
}
return jumps;
}
public class Solution {
public int Jump(int[] nums) {
int currEnd = 0;
int farthest = 0;
int jumps = 0;
for(int i = 0; i < nums.Length - 1; i++) {
farthest = Math.Max(farthest, i + nums[i]);
if(i == currEnd) {
currEnd = farthest;
jumps++;
}
}
return jumps;
}
}
