# 55. Jump Game

## The Problem

Link to original problem on Leetcode.

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

## Examples

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 <= 10`

^{4}`0 <= nums[i] <= 10`

^{5}

## My Solution

### Dynamic Programming

This approach creates an array to store information about whether a given index is reachable or not. We initialize the first value in our `dp`

cache array with the value at `nums[0]`

, as this represents what number index we can reach from the `0`

th index. Then for each index `i`

, we check to see if we had sufficient jump range in `dp[i - 1]`

to reach it, returning `false`

if not. Otherwise, `dp[i]`

will be the larger of `nums[i] + i`

or `dp[i - 1]`

, representing the farthest index we'll be able to reach from position `i`

. If at any point we know we can reach an index farther than the last position of `nums`

, we go ahead and return `true`

. This algorithm has $O(n)$ time complexity and $O(n)$ space complexity.

`function canJump(nums: number[]): boolean {`

const dp: number[] = [];

dp[0] = nums[0];

for (let i = 1; i < nums.length; i++) {

if (dp[i - 1] < i) return false;

dp[i] = Math.max(nums[i] + i, dp[i - 1]);

if (dp[i] >= nums.length - 1) return true;

}

return true;

};

### Greedy Algorithm

This greedy alogorithm is also $O(n)$ time complexity, but only $O(1)$ space complexity because it doesn't need an entire array to keep track of jump ranges. Instead, it optimistically keeps track of the farthest index you can reach in the `nums`

array based on what you've seen so far. If, while iterating over `nums`

, you hit an index greater than the farthest you've been able to reach so far, then you know you'll never reach the end and can return `false`

. Otherwise, you update the range if you've got a new further range, and return if your range can take you to the end.

`function canJump(nums: number[]): boolean {`

// I can get away with naming my jump range variable

// "range" because JavaScript has no `range` function!

// (I weep softly and dream of Python...)

let range = 0;

for (let i = 0; i < nums.length; i++) {

if (range < i) return false;

range = Math.max(nums[i] + i, range);

if (range >= nums.length) return true;

}

return true;

};