## Algorithm

Problem Name: 55. Jump Game

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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

bool canJump0(int* nums, int numsSize) {
if (nums == NULL || numsSize == 0) return false;

/* remain steps from 0 to i */
int *dp = (int *)calloc(numsSize, sizeof(int));
dp[0] = 0;
int i;
for (i = 1; i  <  numsSize; i++) {
if (dp[i - 1] > nums[i - 1]) {
dp[i] = dp[i - 1] - 1;
}
else {
dp[i] = nums[i - 1] - 1;
}
if (dp[i]  <  0) return false;
}

bool can = (dp[numsSize - 1] >= 0);
free(dp);

return can;
}

bool canJump1(int* nums, int numsSize) {
if (nums == NULL || numsSize == 0) return false;

int remain_steps = 0;
int i;
for (i = 1; i  <  numsSize; i++) {
if (remain_steps < nums[i - 1]) {
remain_steps = nums[i - 1] - 1;
}
else {
remain_steps--;
}
if (remain_steps  <  0) return false;
}

return (remain_steps >= 0);
}

bool canJump(int* nums, int numsSize) {
if (nums == NULL || numsSize == 0) return false;

int max_dist = 0; /* max distance we can get */
int i;
/* if we can get to i continue, otherwise exit loop and return false */
for (i = 0; i  <  numsSize && i <= max_dist; i++) {
if (nums[i] + i > max_dist) {
max_dist = nums[i] + i;
}
/* if we already reach the destination, exit loop and return true */
if (max_dist >= numsSize - 1) return true;
}

return false;
}

int main() {

int nums0[] = { 2, 3, 1, 1, 4 };
int nums1[] = { 3, 2, 1, 0, 4 };
int nums2[] = { 2, 5, 0, 0 };
int nums3[] = { 0 };

assert(canJump(nums0, sizeof(nums0) / sizeof(nums0[0])) == true);
assert(canJump(nums1, sizeof(nums1) / sizeof(nums1[0])) == false);
assert(canJump(nums2, sizeof(nums2) / sizeof(nums2[0])) == true);
assert(canJump(nums3, sizeof(nums3) / sizeof(nums3[0])) == true);

printf("all test passed!\n");

return 0;
}
``````
Copy The Code &

Input

cmd
nums = [2,3,1,1,4]

Output

cmd
true

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool canJump(vector<int>& nums) {
int distance = 0;
for(int i = 0; i  <  nums.size() - 1; i++){
distance = max(distance, i + nums[i]);
if(distance == i) return false;
}
return true;
}
};
``````
Copy The Code &

Input

cmd
nums = [3,2,1,0,4

Output

cmd
false

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
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;
}
}

``````
Copy The Code &

Input

cmd
nums = [2,3,1,1,4]

Output

cmd
true

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const canJump = function(nums) {
let max = 0
for(let i = 0, len = nums.length; i  <  len; i++) {
if(i <= max && nums[i] > 0) {
max = Math.max(max, i + nums[i])
}
}
return max >= nums.length - 1
};
``````
Copy The Code &

Input

cmd
nums = [2,3,1,1,4]

Output

cmd
true

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
i = mx = 0
while i < len(nums) and i <= mx:
if nums[i] + i >= len(nums) - 1: return True
mx, i = max(mx, i + nums[i]), i + 1
return False
``````
Copy The Code &

Input

cmd
nums = [3,2,1,0,4]

Output

cmd
false

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _055_JumpGame
{
public bool CanJump(int[] nums)
{
int maxRight = 0;

for (int i = 0; i  <  nums.Length; i++)
{
if (i > maxRight) { return false; }
if (i + nums[i] > maxRight)
maxRight = i + nums[i];
if (maxRight >= nums.Length - 1)
return true;
}

return false;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [3,2,1,0,4]

Output

cmd
false