Minimum Hops: Find the Minimum Number of Jumps to Reach the End of an Array

Question

## Problem

Given an array where each element represents the maximum jump length from that position, find the minimum number of jumps to reach the last index. If it is not possible, return -1.

```python
def min_hops(arr: list[int]) -> int:
    pass
```

**Example:**
```
arr = [2, 3, 1, 1, 4]
-> 2   # 0->1->4 (jump 1, then jump 3)

arr = [2, 3, 0, 1, 4]
-> 2   # 0->1->4

arr = [3, 2, 1, 0, 4]
-> -1  # stuck at index 3 (arr[3]=0)

arr = [0]
-> 0   # already at end
```

## Round 1 - Coding

Implement the greedy O(n) approach tracking the current reach and next reach.

## Follow-ups

1. Explain the greedy algorithm: what do `current_end` and `farthest` track, and why incrementing `jumps` only at `current_end` is correct?
2. How does this differ from the DP approach, and what is each approach's time and space complexity?
3. What if you must return the actual jump sequence, not just the count?
4. How would you extend this to a 2D grid where each cell `(i,j)` allows up to `grid[i][j]` steps right or down?

Minimum Hops: Find the Minimum Number of Jumps to Reach the End of an Array

Question Details

Full Details

Topics

More from Uber