Problem Statement
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Video Solution
Sample Test Cases
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.
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.
Problem Solution
In this Question we will maintain two variables ie. Curr and reachable.
So what we need to do is at any given index we will find the maximum Reachable distance and keep updating it in our reachable variable.
If at any point our current index surpasses the value in reachable then it means that we can’t reach the end of our array and we return false ( Take a look at the gif below for the first test case)
Else if we are able to Traverse the entire array this means that our current index was always less than the reachable and hence we can easily reach the end of the array. Take a look at the gif below for the 2nd test case
Complexity Analysis
Time complexity: O(n) We are doing a single pass through the nums array, hence n steps, where n is the length of the array nums.
Space complexity: O(1) We are not using any extra memory.
#include<bits/stdc++.h>
using namespace std;
bool canJump(vector<int>& nums) {
int reachable=0;
for(int i=0;i<nums.size();i++)
{
if(reachable<i)
{
return false;
}
reachable=max(reachable,i+nums[i]);
}
return true;
}
int main()
{
vector<int>num;
num.push_back(2);
num.push_back(3);
num.push_back(1);
num.push_back(1);
num.push_back(4);
bool ans= canJump(num);
cout<<ans;
}
public class Jump
{
public boolean canJump(int[] nums)
{
if(nums.length < 2)
return true;
for(int curr = nums.length-2; curr>=0;curr--)
{
if(nums[curr] == 0)
{
int neededJumps = 1;
while(neededJumps > nums[curr])
{
neededJumps++;
curr--;
if(curr < 0)
return false;
}
}
}
return true;
}
public static void main(String[] args)
{
Jump m = new Jump();
int arr[] = new int[5];
arr[0] = 2;
arr[1] = 3;
arr[2] = 1;
arr[3] = 1;
arr[4] = 4;
System.out.println(m.canJump(arr));
}
}
def canJump(nums):
if len(nums) == 0:
return False
n_jumps, curr_index = 1, 0
while n_jumps != 0:
if curr_index == len(nums)-1:
return True
n_jumps -= 1
n_jumps = max(nums[curr_index], n_jumps)
curr_index += 1
return False
arr= [2,3,1,1,4]
print(canJump(arr))
