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).

Why this is worth learning

The greedy scan is breadth-first search over reachable index ranges. currentEnd closes one jump layer; farthest accumulates the next layer.

Before coding: one-minute experiment

For [2,3,1,1,4], where do the first and second jump layers end?

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

Initially index zero is the entire zero-jump layer. While scanning positions through currentEnd, farthest records the largest index reachable with one additional jump from any position in this layer. No position beyond currentEnd can be reached using the current number of jumps, by the definition of the layer. Once every position in the layer has been examined, advancing currentEnd to farthest and increasing jumps builds exactly the next BFS layer. The first layer containing the last index therefore uses the fewest jumps. Stopping the scan before the last index avoids charging a jump after arrival; reachability is a precondition.

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).

Debugging lens

An input of length one needs zero jumps. Distinguish currentEnd from farthest: updating the current layer boundary on every iteration can count paths rather than BFS layers.

Complexity

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

Implementation notes (Go)

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

Reconstruction checkpoint

For [2,3,1,1,4], where do the first and second jump layers end?

Return to Array & String · Module quiz