Approach 1: Greedy implementation
Let’s say the range of the current jump is [curBegin, curEnd], curFarthest is the farthest point that all points in [curBegin, curEnd] can reach. Once the current point reaches curEnd, then trigger another jump, and set the new curEnd with curFarthest, then keep the above steps. Consider an example:
Input: [2,3,1,1,4]
Initially, set start = 0, end = 0 and our range is [0,0], i.e., we can only visit the first index.
Now, we take the first step and jump from the first index. The range becomes [0, 2] and curFarthest becomes 2. stepCount = 1
Now, in the range [0, 2], we can jump from the 1st index which can reach till 4th index or jump from the 2nd index which can reach till 3rd index. Clearly, we will choose the one which makes us go farther. So curFarthest would be = 4 and our range will then become [1, 4]. stepCount = 2
Now, we have already reached the last index so we will stop.
int jump(vector<int>& nums) {
if (nums.size()==0)
return 0;
int st = 0, end = 0, res=0, n=nums.size();
for (int i=0; st<n-1; st=end, res++) {
while (i<n && i<=st)
end = max(end, i+nums[i++]);
if (st==end) return -1;
}
return end>=n-1 ? res : -1;
}
Time complexity: O(n)
Approach 2: Thinking as BFS
This approach uses essentially the same greedy approach as above but it’s the way of thinking is a bit different. Suppose the input array is same as above, [2,3,1,1,4]. Let us think of this as a graph where the i-th level has nodes which can be reached by i steps. Let’s not think of any edges right now. The level order traversal (BFS) of the graph graph will be like:
Level 0: 2
Level 1: 3 1
Level 2: 1 4
Clearly, the minimum steps to reach 4 would be the level number, i.e., 2.
// JAVA solution
int jump(int A[], int n) {
if(n<2)return 0;
int level=0,currentMax=0,i=0,nextMax=0;
while(currentMax-i+1>0){ //nodes count of current level>0
level++;
for(;i<=currentMax;i++){ //traverse current level , and update the max reach of next level
nextMax=max(nextMax,A[i]+i);
if(nextMax>=n-1)return level; // if last element is in level+1, then the min jump=level
}
currentMax=nextMax;
}
return 0;
}
Time complexity: O(n)
Recommended: See this solution which thinks of levels in the reverse order (going from the last index to the first)
Approach 3
This question can be converted into LC 1024. Video Stitching. Just convert each jump into a range [i, i+jump[i]] where i is the index. For example, the array of jumps [2,3,1,1,4] can be converted to become [[0,2], [1,4], [2,3], [3,4], [4,8]]. Now the problem reduces to finding minimum number of intervals that cover the entire segment [0, 4].
Recommended: See solution of video stitching.