Lab 02 — Jump Game II

Goal

Internalize the greedy reach pattern: a single forward scan with two pointers (current_end, farthest) producing the minimum number of jumps. Prove correctness via a loop invariant + monovariant pair.

Background

Jump Game II (LC 45) is the canonical “greedy with monovariant” problem. It looks like BFS — and indeed, the greedy is BFS in disguise — but the BFS is implemented in O(n) time and O(1) space because the levels are contiguous index ranges. The proof is a two-part argument: an invariant (“at any point, the farthest position reachable in j jumps equals current_end after the j-th jump”) plus a monovariant (farthest non-decreasing, current_end strictly increasing per jump).

Interview Context

This problem (or its variants — LC 1306, LC 1326, LC 1024) appears at every FAANG-tier interview. The wrong solution is “BFS with a queue, mark visited” (O(n²) time, O(n) space). The right solution looks too simple to be correct unless you have the proof — which is why the interviewer asks for it.

Problem Statement

Given a non-negative integer array nums where nums[i] is the maximum jump length from index i, return the minimum number of jumps to reach the last index, starting from index 0. Assume the last index is always reachable.

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ nums[i] ≤ 1000
  • Last index is always reachable (no -1 case).

Clarifying Questions

  1. “Is 0 a valid value at intermediate positions, and does it mean we get stuck?” — yes; but the problem guarantees reachability, so we won’t actually get stuck.
  2. “Can n == 1? Then the answer is 0 (already at the end).” — yes, edge case to handle.
  3. “Do I return the count of jumps or the path?” — count.
  4. “Are negative jumps allowed?” — no; non-negative only.

Examples

  • [2,3,1,1,4] → 2 (0 → 1 → 4).
  • [2,3,0,1,4] → 2.
  • [1] → 0 (already at end).
  • [1,1,1,1] → 3.
  • [5,1,1,1,1] → 1 (one jump from 0 to 4).

Initial Brute Force

Recursive DP with memoization: dp[i] = min jumps from index i to n-1.

from functools import lru_cache

def jumps_brute(nums):
    n = len(nums)
    @lru_cache(maxsize=None)
    def f(i):
        if i >= n - 1: return 0
        if nums[i] == 0: return float('inf')
        return 1 + min(f(i + j) for j in range(1, nums[i] + 1) if i + j < n)
    return f(0)

Brute Force Complexity

Time O(n · max(nums)) — each cell tried against up to max(nums) next cells. At max(nums) = 1000, that’s 10^7 — borderline. Space O(n) for memo + recursion. The greedy is O(n) time and O(1) space.

Optimization Path

  1. Recursive DP (above) — clear correctness.
  2. Iterative DP — dp[i] filled left to right; dp[i] = 1 + min(dp[i+j]). Same complexity.
  3. BFS — view jumps as edges; level number = answer. O(n²) worst case if naively implemented (revisiting); O(n) if you track the boundary. The boundary tracking is exactly the greedy.
  4. Greedy with two pointers — O(n) time, O(1) space. The BFS layers are contiguous ranges [L, R]; we process the range and compute the next range’s right endpoint as max(i + nums[i]) for i ∈ [L, R].

Final Expected Approach

def jump(nums):
    n = len(nums)
    if n <= 1: return 0
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(n - 1):              # don't iterate past n-1
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if current_end >= n - 1:
                break
    return jumps

Two pointers: current_end is the right boundary of the BFS layer we’re currently processing; farthest is the right boundary of the next BFS layer being assembled.

Data Structures Used

  • Three integers: jumps, current_end, farthest. No arrays, no queue, no recursion. The simplicity is the point.

Correctness Argument

We prove: at termination, jumps equals the minimum number of jumps to reach index n - 1.

Setup. Define level(j) = the set of indices reachable from 0 in exactly j jumps and not in fewer. By induction on j: level(0) = {0}; level(j+1) = {i + k : i ∈ level(j), 1 ≤ k ≤ nums[i]} − ⋃_{j' ≤ j} level(j'). By a simple induction, level(j+1) is a contiguous range of indices [L_{j+1}, R_{j+1}] immediately to the right of R_j. (Proof: level(j) is contiguous by induction; the union of [i, i + nums[i]] over i in a contiguous range is itself a contiguous range; subtracting earlier levels removes a contiguous prefix.)

Loop invariant. At the top of iteration i:

  1. current_end = R_{jumps} — i.e., the right boundary of the layer reached in jumps jumps so far.
  2. farthest = max_{k ≤ i, k ≤ current_end} (k + nums[k]) — the farthest reachable from any index processed so far in the current layer.

Initialization. Before the loop: jumps = 0, current_end = 0, farthest = 0. Layer 0 is {0} with R_0 = 0 ✓.

Maintenance. At iteration i:

  • We update farthest = max(farthest, i + nums[i]). If i ≤ current_end, this maintains invariant (2).
  • If i == current_end, we’ve finished processing the current layer. We “jump”: jumps += 1, current_end = farthest. By invariant (2), farthest = R_{jumps_old + 1} = right boundary of the next layer. So invariant (1) is restored with jumps_new = jumps_old + 1.

Monovariant. farthest is non-decreasing across the loop (each iteration takes a max). At each “jump” event, current_end strictly increases (otherwise the last index isn’t reachable, contradicting the problem’s guarantee). The loop runs n - 1 iterations and the number of “jump” events is bounded above by n - 1, so the algorithm terminates and produces a finite jumps value.

Termination + correctness. The loop terminates after n - 1 iterations (or earlier if current_end ≥ n - 1). At that point, current_end ≥ n - 1 (because the last index is reachable; if it weren’t, we’d have current_end < n - 1 and farthest = current_end — no progress — but the problem guarantees reachability, so farthest > current_end whenever current_end < n - 1). Therefore jumps is exactly the layer index of n - 1 in the BFS — i.e., the minimum jump count. QED.

The two key proof devices: the invariant that current_end tracks layer boundaries, and the monovariant that farthest is non-decreasing. Together they give correctness; the monovariant alone gives termination.

Complexity

  • Time O(n) — single forward scan.
  • Space O(1) — three integers.

Implementation Requirements

  • Loop bound i < n - 1, not i < n. Iterating to n - 1 would cause an extra spurious jump count when current_end == n - 1.
  • if i == current_end: — the trigger for layer transition. The check happens after farthest is updated.
  • if current_end >= n - 1: break — early exit.
  • Handle n == 1 as a special case (answer 0) before the loop.

Tests

def test_jump():
    assert jump([2,3,1,1,4]) == 2
    assert jump([2,3,0,1,4]) == 2
    assert jump([1]) == 0
    assert jump([1,1,1,1]) == 3
    assert jump([5,1,1,1,1]) == 1
    assert jump([1,2]) == 1
    assert jump([0]) == 0  # n=1, no jumps needed
    # large jump from start
    assert jump([100, 1, 1, 1, 1, 1, 1]) == 1

Stress-test versus the recursive DP for n ≤ 20.

Follow-up Questions

  • LC 55 (Jump Game I) — can we reach the end? farthest ≥ i invariant suffices.
  • LC 1306 (Jump Game III) — bidirectional jumps with fixed offsets; not greedy, BFS.
  • LC 1340 (Jump Game V) — descent-only, weighted; DP territory.
  • Min jumps with cost — DP, not greedy. The cost asymmetry breaks the layer-contiguity argument.

Product Extension

Network packet routing: minimum hops to reach a destination when each node has a maximum forward-reach. Game pathfinding when movement primitives have variable range.

Language / Runtime Follow-ups

  • Python: as shown above. Beware the off-by-one on range(n - 1).
  • Java: int n = nums.length; if (n <= 1) return 0; int jumps = 0, end = 0, far = 0; for (int i = 0; i < n - 1; i++) { far = Math.max(far, i + nums[i]); if (i == end) { jumps++; end = far; if (end >= n - 1) break; } }.
  • Go: identical structure; use if i+nums[i] > far { far = i + nums[i] } to avoid math.Max float overhead.
  • C++: same; use std::max.
  • JS/TS: same; Math.max(...). Watch for nums.length re-evaluation cost in tight loops on engines that don’t hoist.

Common Bugs

  • Iterating for i in range(n) and double-counting the last jump.
  • Updating current_end before the bookkeeping check i == current_end.
  • Forgetting the n == 1 early return.
  • Using BFS with a queue when the contiguous-range observation makes it O(1) space.
  • Confusing farthest (assembling next layer) with current_end (current layer’s right edge) — labelling them consistently is essential.

Debugging Strategy

  • Print (i, current_end, farthest, jumps) at each iteration on a small input. The state should evolve predictably: farthest rises, current_end jumps to farthest exactly when i catches up.
  • If your output is one too many: check the loop bound (n - 1 not n).
  • If your output is one too few: check that you increment jumps at the layer boundary, not after the last iteration.

Mastery Criteria

  • You can write the algorithm in <5 minutes from blank.
  • You can articulate the BFS-layer interpretation in <30 seconds.
  • You can state the loop invariant precisely and run through initialization → maintenance → termination in <2 minutes.
  • You can name the monovariant and explain why it implies termination, in <30 seconds.
  • You can extend to LC 55 (Jump Game I) in <3 minutes by simplifying the same template.

← Lab 01 — Interval Scheduling · Phase 6 README · Lab 03 — Task Scheduler →