Jump Game Leetcode Solution
Jump Game Leetcode Problem :
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Jump Game Leetcode Solution :
Constraints :
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 105
Example 1:
- Input: nums = [3,2,1,0,4]
- Output: false
- Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Intuition :
The basic idea is this: at each step, we keep track of the furthest reachable index. The nature of the problem (eg. maximal jumps where you can hit a range of targets instead of singular jumps where you can only hit one target) is that for an index to be reachable, each of the previous indices have to be reachable.
Approach :
Hence, it suffices that we iterate over each index, and If we ever encounter an index that is not reachable, we abort and return false. By the end, we will have iterated to the last index. If the loop finishes, then the last index is reachable.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
bool canJump(vector& nums) {
int n = nums.size();
int maxReach = 0;
for (int i = 0; i < n; i++) {
if (i > maxReach) return false;
maxReach = max(maxReach, i + nums[i]);
}
return true;
}
};
class Solution {
public boolean canJump(int[] nums) {
int reachable = 0;
for(int i = 0; i < nums.length; i ++) {
if(i > reachable) return false;
reachable = Math.max(reachable, i + nums[i]);
}
return true;
}
}
class Solution:
def canJump(self, nums: List[int]) -> bool:
reach = 0
for i in range(len(nums)):
if i > reach or reach >= len(nums) - 1:
break
reach = max(reach, i + nums[i])
return reach >= len(nums) - 1
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment