# LeetCode 55: Jump Game

## Problem Restatement

We are given an integer array `nums`.

We start at index `0`. Each value `nums[i]` tells us the maximum number of steps we can jump forward from index `i`.

We need to return `true` if we can reach the last index. Otherwise, return `false`.

The official constraints are `1 <= nums.length <= 10^4` and `0 <= nums[i] <= 10^5`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | `true` if the last index is reachable, otherwise `false` |
| Start | Index `0` |
| Jump rule | From index `i`, we may jump at most `nums[i]` steps forward |

Function shape:

```python
def canJump(nums: list[int]) -> bool:
    ...
```

## Examples

For:

```python
nums = [2, 3, 1, 1, 4]
```

The answer is:

```python
True
```

One valid path is:

```text
index 0 -> index 1 -> index 4
```

At index `0`, `nums[0] = 2`, so we can jump to index `1`.

At index `1`, `nums[1] = 3`, so we can jump to the last index.

For:

```python
nums = [3, 2, 1, 0, 4]
```

The answer is:

```python
False
```

We can reach index `3`, but `nums[3] = 0`.

From index `3`, we cannot move forward, so index `4` cannot be reached.

## First Thought: Try Every Jump

A direct approach is to try every possible jump from every reachable index.

For example, from index `i`, we can try:

```text
i + 1
i + 2
...
i + nums[i]
```

Then recursively check whether any of those choices can reach the last index.

This approach is natural, but it can repeat a lot of work. Many different paths may reach the same index, and then solve the same subproblem again.

## Key Insight

We do not need to remember every path.

We only need to remember the farthest index we can reach so far.

Call this value:

```python
farthest
```

As we scan the array from left to right:

1. If the current index is greater than `farthest`, we cannot even stand on this index.
2. If we can stand on this index, then we can use `nums[i]` to possibly extend `farthest`.

The update is:

```python
farthest = max(farthest, i + nums[i])
```

If at any point `farthest` reaches or passes the last index, the answer is `True`.

## Algorithm

Initialize:

```python
farthest = 0
```

Then scan each index `i`.

For each index:

1. If `i > farthest`, return `False`.
2. Update `farthest` with `i + nums[i]`.
3. If `farthest >= len(nums) - 1`, return `True`.

If the loop finishes, return `True`.

## Correctness

At any point during the scan, `farthest` means the largest index reachable using only positions we have already processed.

Initially, only index `0` is reachable, so `farthest = 0`.

When we process index `i`, there are two cases.

If `i > farthest`, then index `i` cannot be reached from any earlier position. Since we scan from left to right, every later index is even farther away. Therefore the last index cannot be reached, and returning `False` is correct.

If `i <= farthest`, then index `i` is reachable. From index `i`, we may jump as far as `i + nums[i]`. Updating `farthest` with the maximum of the old value and this new reach preserves the meaning of `farthest`.

If `farthest >= len(nums) - 1`, the last index is reachable, so returning `True` is correct.

Therefore the algorithm returns `True` exactly when the last index can be reached.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We keep only one integer |

## Implementation

```python
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        farthest = 0
        last = len(nums) - 1

        for i, jump in enumerate(nums):
            if i > farthest:
                return False

            farthest = max(farthest, i + jump)

            if farthest >= last:
                return True

        return True
```

## Code Explanation

We start with:

```python
farthest = 0
```

This means we can reach index `0` at the beginning.

We also store the last index:

```python
last = len(nums) - 1
```

Then we scan each index and jump value:

```python
for i, jump in enumerate(nums):
```

Before using `nums[i]`, we must confirm that index `i` is reachable:

```python
if i > farthest:
    return False
```

If `i` is reachable, then from `i` we may reach up to:

```python
i + jump
```

So we update:

```python
farthest = max(farthest, i + jump)
```

Once `farthest` reaches the last index, we can stop immediately:

```python
if farthest >= last:
    return True
```

The final return handles the case where the loop completes normally:

```python
return True
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.canJump([2, 3, 1, 1, 4]) is True
    assert s.canJump([3, 2, 1, 0, 4]) is False
    assert s.canJump([0]) is True
    assert s.canJump([0, 1]) is False
    assert s.canJump([2, 0, 0]) is True
    assert s.canJump([1, 0, 1, 0]) is False
    assert s.canJump([4, 0, 0, 0, 0]) is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[2,3,1,1,4]` | Reachable standard example |
| `[3,2,1,0,4]` | Blocked by zero |
| `[0]` | Already at the last index |
| `[0,1]` | Cannot move from the first index |
| `[2,0,0]` | Jump can pass over zeros |
| `[1,0,1,0]` | Gets stuck before the end |
| `[4,0,0,0,0]` | One jump can reach the last index |