In the Leetcode Jump Game problem solution, 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.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
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.
Constraints:
- 1 <= nums.length <= 104
- 0 <= nums[i] <= 105
Solution in C Programming
bool canJump(int* nums, int numsSize){
if(numsSize==1)
{
return true;
}
if(nums[0]==0)
{
return false;
}
int maxDistance=0;
for(int i=0; i<numsSize-1; i++)
{
//At each index we find the max reachable distance
//If at the end the maxDistance>=numsSize-1 then we return true else false
//If index i is greater than the maxDistance then we return false
if(i>maxDistance)
{
return false;
}
//If the current max jump is greater than the maxDistance then change the maxDistance
if((i+nums[i])>maxDistance)
{
maxDistance=i+nums[i];
}
}
if(maxDistance>=numsSize-1)
{
return true;
}
return false;
}Solution in C++ Programming
class Solution {
public:
bool canJump(vector<int>& nums) {
int target = nums.size()-1;
for(int i = target-1; i >= 0; i--){
if(nums[i]+i >= target) target = i;
}
return target == 0;
}
};Solution in Java Programming
class Solution {
public boolean canJump(int[] nums) {
int max = 0;
for(int i = 0; i < nums.length; i++){
if(i > max) return false;
max = Math.max(nums[i] + i, max);
}
return true;
}
}Solution in Python Programming
class Solution:
def canJump(self, nums):
def bt(index):
if index == len(nums)-1:
return True
if index >= len(nums):
return
for i in range(1, nums[index]+1):
if bt(index+i) == True:
return True
return bt(0)Solution in C# Programming
public class Solution {
public bool CanJump(int[] nums) {
if (nums.Length == 1)
return true;
int goal = nums.Length - 1;
int i = goal - 1;
while (i >= 0) {
if (nums[i] + i >= goal) {
goal = i;
}
i--;
}
return goal == 0;
}
}Also read,