 # Jump Game

## 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.

## 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;
arr = 2;
arr = 3;
arr = 1;
arr = 1;
arr = 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))```

Scroll to Top