Jump Game Minimum Jumps

Find the minimum number of jumps to reach the last index.

arrays greedy minimum-jumps sliding-window

You are given a 0-indexed array `nums` of non-negative integers. You start at index 0. Each element `nums[i]` represents your maximum jump length from index `i`. In other words, if you are at index `i`, you can jump to any index `i + j` where `1 <= j <= nums[i]` and `i + j < len(nums)`.

Write a function `min_jumps(nums)` that returns the minimum number of jumps required to reach the last index. If the last index is unreachable, return `-1`.

**Function signature:**
```python
def min_jumps(nums: list[int]) -> int:
```

**Assumptions:**
- `nums` has at least one element.
- Each element is a non-negative integer.
- Index 0 is always reachable (starting position).

Constraints

- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 10^5`
- The solution should run in O(n) time and O(1) extra space.

Example

>>> min_jumps([2,3,1,1,4])
2
>>> min_jumps([2,3,0,1,4])
2
>>> min_jumps([1,1,1,1])
3
>>> min_jumps([3,2,1,0,4])
-1
>>> min_jumps([0])
0

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a window of reachable indices for the current jump count. Expand the farthest reachable index after each jump.

Iterate through the array once, tracking the current window's end and the farthest index reachable within that window.

When you exhaust the current window (i == current_end), increment the jump count and move the window to the farthest reachable index.

If at any point the farthest reachable index is less than or equal to the current index and you're not at the end, return -1.

The answer is the number of times you move to a new window before reaching the last index.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.