Jump Game — Greedy Reachability
Sanjeev SharmaAdvertisement
Problem
Each nums[i] is maximum jump from index i. Can you reach the last index?
Approach — Greedy
Track reach = max reachable index. If i > reach at any point, return False.
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def canJump(self, nums: list[int]) -> bool:
reach=0
for i,n in enumerate(nums):
if i>reach: return False
reach=max(reach,i+n)
return True
C++
class Solution {
public:
bool canJump(vector<int>& nums){
int reach=0;
for(int i=0;i<nums.size();i++){
if(i>reach) return false;
reach=max(reach,i+nums[i]);
}
return true;
}
};
Java
class Solution {
public boolean canJump(int[] nums){
int reach=0;
for(int i=0;i<nums.length;i++){
if(i>reach) return false;
reach=Math.max(reach,i+nums[i]);
}
return true;
}
}
Complexity
- Time: O(n) | Space: O(1)
Advertisement
