216. Minimum Jumps to End

Why this mechanism works

Compress BFS into index ranges. Every index through end is reachable within the current jump budget. While scanning that layer, collect the farthest destination available for one additional jump. Increase the jump count only when the current layer boundary is exhausted.

State and boundaries

end is the farthest index reachable with jumps jumps. farthest accumulates the next layer's boundary from scanned reachable positions.

Protocol

1. Handle empty/singleton cases.
2. Scan only positions before the destination.
3. Extend farthest.
4. At i==end reject a nonexpanding frontier.
5. Otherwise add one jump and move end to farthest.
6. Return when end covers the destination.

Visualization

[2,3,1,1,4]
zero-jump boundary 0
after first layer: boundary 2, jumps 1
scan indices 1..2 -> boundary 4, jumps 2

Python implementation

def min_jumps(nums):
    if not nums:
        return -1
    if len(nums) == 1:
        return 0
    jumps = end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:
            if farthest == end:
                return -1
            jumps += 1
            end = farthest
            if end >= len(nums) - 1:
                return jumps
    return -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 min_jumps: if not nums:
nums=[2, 3, 1, 1, 4]

L6 min_jumps: jumps = end = farthest = 0
nums=[2, 3, 1, 1, 4]; jumps=0; end=0; farthest=0

L7 min_jumps: for i in range(len(nums) - 1):
nums=[2, 3, 1, 1, 4]; jumps=0; end=0; farthest=0; i=0

L8 min_jumps: farthest = max(farthest, i + nums[i])
nums=[2, 3, 1, 1, 4]; jumps=0; end=0; farthest=2; i=0

L12 min_jumps: jumps += 1
nums=[2, 3, 1, 1, 4]; jumps=1; end=0; farthest=2; i=0

L13 min_jumps: end = farthest
nums=[2, 3, 1, 1, 4]; jumps=1; end=2; farthest=2; i=0

L7 min_jumps: for i in range(len(nums) - 1):
nums=[2, 3, 1, 1, 4]; jumps=1; end=2; farthest=2; i=1

L8 min_jumps: farthest = max(farthest, i + nums[i])
nums=[2, 3, 1, 1, 4]; jumps=1; end=2; farthest=4; i=1

L7 min_jumps: for i in range(len(nums) - 1):
nums=[2, 3, 1, 1, 4]; jumps=1; end=2; farthest=4; i=2

L12 min_jumps: jumps += 1
nums=[2, 3, 1, 1, 4]; jumps=2; end=2; farthest=4; i=2

L13 min_jumps: end = farthest
nums=[2, 3, 1, 1, 4]; jumps=2; end=4; farthest=4; i=2

L2 min_jumps: if not nums:
nums=[0]

Why the solution is correct

The first frontier represents zero jumps. Scanning every position in a layer discovers exactly all destinations obtainable with one additional jump. Advancing layers therefore follows minimum jump count just as BFS does. A frontier that cannot expand proves the destination unreachable.

Time and space

O(n) time and O(1) auxiliary state.

Common mistakes

Increasing jumps at every index counts explored positions instead of BFS layers. Processing the final destination as another departure can add an unnecessary jump.

Reasoning card

Transfer exercise

Record which index extends each frontier furthest to reconstruct one minimum-jump route.