# LeetCode 45: Jump Game II

## Problem Restatement

We are given a 0-indexed integer array `nums`.

We start at index `0`.

Each value `nums[i]` tells us the maximum jump length from index `i`. From index `i`, we may jump to any index from `i + 1` up to `i + nums[i]`, as long as the index is inside the array.

We need to return the minimum number of jumps needed to reach the last index.

The test cases guarantee that the last index is reachable.

Example:

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

The answer is:

```python
2
```

One optimal path is:

```python
0 -> 1 -> 4
```

From index `0`, jump to index `1`.

From index `1`, jump to the last index.

Another example:

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

The answer is also:

```python
2
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Minimum number of jumps to reach the last index |
| Start | Index `0` |
| Goal | Index `len(nums) - 1` |
| Guarantee | The last index is always reachable |

Function shape:

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

## First Thought: Dynamic Programming

A direct way is to define:

```python
dp[i] = minimum jumps needed to reach index i
```

Start with:

```python
dp[0] = 0
```

Then for every index `i`, try all jumps from `i`.

If we can jump from `i` to `j`, update:

```python
dp[j] = min(dp[j], dp[i] + 1)
```

This works, but it can be slow.

In the worst case, each index can jump to many later indices, so this approach can take `O(n^2)` time.

We need a linear approach.

## Key Insight

Think of jumps as ranges.

After `0` jumps, we are at index `0`.

After `1` jump, we can reach every index from `1` up to `nums[0]`.

While scanning this current reachable range, we compute the farthest index reachable with one more jump.

When we finish scanning the current range, we must make another jump.

So we track three values:

| Variable | Meaning |
|---|---|
| `jumps` | Number of jumps used so far |
| `current_end` | End of the range reachable with `jumps` jumps |
| `farthest` | Farthest index reachable with `jumps + 1` jumps |

This is like breadth-first search over ranges, but without an explicit queue.

## Algorithm

Initialize:

```python
jumps = 0
current_end = 0
farthest = 0
```

Scan indices from `0` to `len(nums) - 2`.

We stop before the last index because once we can reach the last index, no further jump is needed from it.

At each index `i`, update:

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

This means: from all positions inside the current jump range, what is the farthest next position we can reach?

If we reach the end of the current range:

```python
if i == current_end:
```

then we need to commit to another jump:

```python
jumps += 1
current_end = farthest
```

At the end, return `jumps`.

## Walkthrough

Use:

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

Start:

```python
jumps = 0
current_end = 0
farthest = 0
```

At index `0`:

```python
farthest = max(0, 0 + 2) = 2
```

Now `i == current_end`, so we have finished the range reachable with `0` jumps.

We make one jump:

```python
jumps = 1
current_end = 2
```

This means with `1` jump, we can reach any index up to `2`.

Now scan indices `1` and `2` to find the best range for the next jump.

At index `1`:

```python
farthest = max(2, 1 + 3) = 4
```

At index `2`:

```python
farthest = max(4, 2 + 1) = 4
```

Now `i == current_end`, so we have finished the range reachable with `1` jump.

We make another jump:

```python
jumps = 2
current_end = 4
```

Index `4` is the last index, so the answer is:

```python
2
```

## Correctness

The algorithm processes the array in ranges.

At any moment, `current_end` marks the farthest index reachable using exactly `jumps` jumps or fewer. Every index up to `current_end` is part of the current reachable layer.

While scanning this layer, the algorithm computes `farthest`, the farthest index reachable using one additional jump from any index in the layer.

When the scan reaches `current_end`, all choices for the current number of jumps have been considered. To go farther, one more jump is necessary. Updating `current_end = farthest` creates the next reachable layer.

Because the algorithm only increases `jumps` after exhausting all positions reachable with the previous number of jumps, the first time the range reaches the last index, it has used the minimum possible number of jumps.

The problem guarantees reachability, so the process always reaches the last index.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index is scanned once |
| Space | `O(1)` | Only three variables are used |

## Implementation

```python
class Solution:
    def jump(self, nums: list[int]) -> int:
        jumps = 0
        current_end = 0
        farthest = 0

        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])

            if i == current_end:
                jumps += 1
                current_end = farthest

        return jumps
```

## Code Explanation

We begin with no jumps:

```python
jumps = 0
```

At the start, the current reachable range ends at index `0`:

```python
current_end = 0
```

The best next reach also starts at `0`:

```python
farthest = 0
```

Then we scan up to the second-to-last index:

```python
for i in range(len(nums) - 1):
```

We do not need to jump from the last index.

At each index, we update the farthest place reachable by one more jump:

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

When we reach the boundary of the current jump range:

```python
if i == current_end:
```

we must use another jump:

```python
jumps += 1
current_end = farthest
```

At the end, `jumps` is the minimum number of jumps needed to reach the last index.

## Testing

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

    assert s.jump([2, 3, 1, 1, 4]) == 2
    assert s.jump([2, 3, 0, 1, 4]) == 2
    assert s.jump([0]) == 0
    assert s.jump([1, 2]) == 1
    assert s.jump([1, 1, 1, 1]) == 3
    assert s.jump([4, 1, 1, 1, 1]) == 1
    assert s.jump([2, 1, 1, 1, 1]) == 3

    print("all tests passed")

run_tests()
```

| Test | Expected | Reason |
|---|---:|---|
| `[2, 3, 1, 1, 4]` | `2` | Standard example |
| `[2, 3, 0, 1, 4]` | `2` | Zero inside reachable path |
| `[0]` | `0` | Already at the last index |
| `[1, 2]` | `1` | One jump reaches the end |
| `[1, 1, 1, 1]` | `3` | Must move one step at a time |
| `[4, 1, 1, 1, 1]` | `1` | First jump reaches the end |
| `[2, 1, 1, 1, 1]` | `3` | Greedy range expansion required |