# 0055. Jump Game

https://leetcode.com/problems/jump-game

## Description

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`

## ac1

acepted, but ugly\
corner case is tedious

```java
class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 0) return false;
        if (nums.length == 1) return true;
        // start backwards
        // meet 0, raise zeroBlock
        // check current step can jump over zeroBlock, i + val > zeroBlock
        int zeroBlock = -1;
        for (int i = nums.length - 1 - 1; i >= 0; i--) {
            if (nums[i] == 0 && zeroBlock == -1) {
                zeroBlock = i;
                continue;
            }
            if (zeroBlock == -1) continue;
            if (nums[i] + i > zeroBlock) {
                zeroBlock = -1;
            }
        }

        return zeroBlock == -1;
    }
}
```

## ac2

This one is concise and beautiful.

```java
class Solution {
    public boolean canJump(int[] nums) {
        int reachable = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] + i >= reachable) reachable = i;
        }
        return reachable == 0;
    }
}
```
