Jump Game II — Minimum Jumps Greedy
Sanjeev SharmaAdvertisement
Problem
Find minimum jumps to reach nums[n-1]. (Always possible.)
Approach — Greedy Jump Counting
Track current boundary and farthest. When we exhaust current boundary, increment jumps and extend to farthest.
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def jump(self, nums: list[int]) -> int:
jumps=farthest=curr_end=0
for i in range(len(nums)-1):
farthest=max(farthest,i+nums[i])
if i==curr_end:
jumps+=1; curr_end=farthest
return jumps
C++
class Solution {
public:
int jump(vector<int>& nums){
int jumps=0,farthest=0,curr=0;
for(int i=0;i<nums.size()-1;i++){
farthest=max(farthest,i+nums[i]);
if(i==curr){jumps++;curr=farthest;}
}
return jumps;
}
};
Java
class Solution {
public int jump(int[] nums){
int jumps=0,farthest=0,curr=0;
for(int i=0;i<nums.length-1;i++){
farthest=Math.max(farthest,i+nums[i]);
if(i==curr){jumps++;curr=farthest;}
}
return jumps;
}
}
Complexity
- Time: O(n) | Space: O(1)
Advertisement
← Previous
Decode Ways — Counting DP