Jump Game II

You are given an array nums where nums[i] is the maximum jump length from index i. Starting at index 0, return the minimum number of jumps required to reach the last index. You may assume the last index is always reachable.

A BFS over indices works but is too slow if done explicitly. A greedy approach simulates BFS levels in O(n).

Function signature

func MinJumps(nums []int) int

Inputs / outputs

• nums: non-empty slice of non-negative integers.
• Return: the minimum number of jumps to reach the last index.

Example

nums = [2,3,1,1,4]
Output: 2

Reason: jump from 0 -> 1 -> 4.

Constraints

• 1 <= len(nums) <= 100_000
• 0 <= nums[i] <= 1_000_000_000
• The last index is reachable.

Core idea (near-solution)

Think of reachable indices in layers (like BFS), but track them using two pointers:

• currentEnd: the farthest index reachable using the current number of jumps.
• farthest: the farthest index reachable by taking one more jump from any index in the current layer.

Invariant: when you reach currentEnd, you have finished one layer and must increase the jump count.

Algorithm (step-by-step)

1. If len(nums) <= 1, return 0.
2. Initialize jumps = 0, currentEnd = 0, farthest = 0.
3. For each index i from 0 to len(nums)-2:
   • Update farthest = max(farthest, i + nums[i]).
   • If i == currentEnd, you have exhausted the current layer:
     • Increment jumps.
     • Set currentEnd = farthest.
4. Return jumps.

Correctness sketch

• Invariant: when you reach currentEnd, you have finished one layer and must increase the jump count.
• The algorithm maintains a feasible best-so-far state while scanning.
• Each greedy update preserves feasibility and never discards a possible optimal answer.
• When the scan ends, the recorded state represents the optimal solution.

Trace (hand walkthrough)

Example input:
nums = [2,3,1,1,4]
Output: 2

Reason: jump from 0 -> 1 -> 4.

Walk:
- i=0: farthest=2; i==currentEnd(0) -> jumps=1, currentEnd=2
- i=1: farthest=max(2,1+3)=4
- i=2: farthest=4; i==currentEnd(2) -> jumps=2, currentEnd=4
- reach end with 2 jumps

Pitfalls to avoid

• Incrementing jumps on every index instead of only at currentEnd.
• Iterating all the way to the last index (you don't need to jump from the last).

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Use len(nums)-1 as the target index.