jump-game-ii

Difficulty: Medium · Topic: 1-D Dynamic Programming · Practice it on parikshan: /practice/jump-game-ii/start

The story

Google Maps serves a route that crosses many road segments. Each segment provides a "look-ahead radius" inside which a manoeuvre is permissible without re-routing (lane change radius, intersection consolidation, turn lookahead). The mapping pipeline asks: given those per-segment radii, what is the minimum number of manoeuvres required to traverse the whole route end-to-end? Each manoeuvre commits to a forward stretch up to that segment's radius; you want the fewest commitments.

That count is jump-game-ii. Once you see the framing, the same pattern appears in CI/CD pipeline staging (minimum number of release waves to reach the final stage given per-stage fan-out), data centre routing wave counts at Cloudflare, hop-count minimisation in firmware OTA rollouts on Amazon Devices, and BFS layer counts in any "reach the destination in the fewest moves" puzzle.

This problem is jump-game's ambitious sibling. The shape is the same; the answer is "how many" instead of "yes or no". The clean solution is a BFS-flavoured greedy in disguise, and the disguise is the entire interview lesson.

What's actually being asked

You have a non-negative integer array nums of length n. You start at index 0. From index i you may jump to any index in [i+1, i+nums[i]]. Assume the last index is always reachable. Return the minimum number of jumps to reach n - 1.

Examples:

nums = [2, 3, 1, 1, 4] → 2. Jump 0 → 1 (one jump), then 1 → 4 (two jumps). Done.
nums = [2, 3, 0, 1, 4] → 2. Same two-jump structure.
nums = [1] → 0. Already at the last index; no jumps taken.
nums = [1, 2, 1, 1, 1] → 3.

The naive approach

Recursion: at each index, branch on every legal jump length, take the minimum:

def jumps(i, nums):
    if i >= len(nums) - 1: return 0
    best = float('inf')
    for k in range(1, nums[i] + 1):
        best = min(best, 1 + jumps(i + k, nums))
    return best

Exponential without memoisation, O(n²) with. At n = 10⁵, O(n²) is 10¹⁰ ops; TLE.

The key insight

Think of the indices as nodes in a graph, with an edge from i to every index in [i+1, i+nums[i]]. The number of jumps to reach n-1 is the shortest-path distance in this unweighted graph. BFS solves it in O(V+E), but the edge count can be O(n²), so naive BFS is no better than DP.

The trick: BFS visits indices in layers (all indices reachable in k jumps, for each k). At every layer the reachable indices form a contiguous interval [L_k, R_k]. Why? Because if you can reach index j in k jumps, you can also reach j+1, j+2, ..., j + nums[j] in k+1 jumps; intermediate indices stay reachable. So layer k+1's right edge is R_{k+1} = max_{i in [L_k, R_k]} (i + nums[i]). The left edge is L_{k+1} = R_k + 1 (you cannot stay at the same place).

Collapse BFS to two integers: cur_end (right edge of the current layer) and farthest (best lookahead seen so far in the current layer). When i crosses cur_end, you have exhausted the current layer; commit a jump and slide cur_end to farthest.

# BFS-flavoured greedy recurrence:
# jumps = 0, cur_end = 0, farthest = 0
# For i from 0 to n-2:
#   farthest = max(farthest, i + nums[i])
#   if i == cur_end:
#     jumps += 1
#     cur_end = farthest
#     if cur_end >= n - 1: break
# Answer = jumps

The four DP questions, in collapsed BFS form:

State: a pair of integers, cur_end (boundary of the current jump-count layer) and farthest (the maximum reach across all positions seen in the current layer).
Base case: cur_end = 0, farthest = 0, jumps = 0.
Transition: walk i left to right; track farthest; when i reaches cur_end, commit a jump (jumps += 1) and advance cur_end = farthest.
Answer: jumps, computed once the loop ends or cur_end >= n - 1.

Notice: the loop ranges over i = 0..n-2 (not n-1). The last index is the destination; we count jumps taken, not jumps available once we arrive.

Step-by-step approach

def min_jumps(nums):
    n = len(nums)
    if n <= 1:
        return 0
    jumps = 0
    cur_end = 0
    farthest = 0
    for i in range(n - 1):
        if i + nums[i] > farthest:
            farthest = i + nums[i]
        if i == cur_end:
            jumps += 1
            cur_end = farthest
            if cur_end >= n - 1:
                break
    return jumps

O(n) time, O(1) space. One pass.

The DP form (O(n²), for the educational walk):

def min_jumps_dp(nums):
    n = len(nums)
    INF = n + 1
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for k in range(1, nums[i] + 1):
            if i + k < n and dp[i] + 1 < dp[i + k]:
                dp[i + k] = dp[i] + 1
    return dp[n-1]

Useful to verify the greedy on small inputs; never ship it.

Worked example

nums = [2, 3, 1, 1, 4], n = 5

i	nums[i]	farthest (before)	i + nums[i]	farthest (after)	i == cur_end?	jumps	cur_end	break?
0	2	0	2	2	0 == 0 yes	1	2	2 >= 4? no
1	3	2	4	4	1 == 2 no	1	2	.
2	1	4	3	4	2 == 2 yes	2	4	4 >= 4 yes → break

Return 2. Verified.

Visualising the layers:

Layer 0 (0 jumps): {0}. From 0, you can reach up to index 2.
Layer 1 (1 jump): {1, 2}. From here, the best reach is max(1+3, 2+1) = 4.
Layer 2 (2 jumps): {3, 4}. 4 is the destination.

The BFS layers are exactly what cur_end tracks.

Complexity

DP: O(n²) time, O(n) space.
Greedy: O(n) time, O(1) space.

Always ship the greedy.

Common pitfalls

Looping to n-1 inclusive: causes an off-by-one extra jump count. If cur_end happens to equal n-1, the loop commits one extra jump at the end. Loop over range(n-1).
Wrong n == 1 handling: starting at the last index requires zero jumps. If your code unconditionally increments, it reports 1. Guard with if n <= 1: return 0.
Mixing up cur_end and farthest: cur_end is the right boundary of the committed layer; farthest is the right boundary of the next layer being assembled. They are different. Swap them and you commit jumps prematurely.
Bumping jumps outside the boundary check: if you do jumps += 1 on every iteration, you count the wrong thing.

Where this shows up in the enterprise

Google Maps routing: minimum manoeuvres / lane changes / turns to traverse a corridor.
Cloudflare data centre routing: minimum hop count across a topology where each hop has a fan-out budget.
PagerDuty escalation depth: minimum escalation levels to reach the on-call owner.
Amazon Devices firmware OTA: minimum rollout waves to cover all leaf devices given per-gateway fan-out.
Spotify Wrapped story compilation: minimum slide layers to cover an annual narrative arc.
Speech recognition (Apple Siri, Google Assistant) Viterbi pruning: minimum decoder beams to traverse a phoneme lattice end-to-end.
Build / CI staging at Stripe and Shopify: minimum release waves to roll out a feature across services with bounded blast radius per wave.

The shape, minimum number of unweighted hops across a graph whose adjacency is "everything within a range", is everywhere.

Variants you'll see elsewhere

jump-game: the reachability twin; one less number to track.
jump-game-iii: each index allows exactly two jumps (±nums[i]); find any index with value 0. Classic BFS, no greedy collapse.
jump-game-iv: BFS with adjacency by value equality and immediate neighbours.
jump-game-vii: substring jumps with character constraints; sliding-window BFS.
minimum-number-of-taps-to-water-a-garden: rephrase intervals as jump ranges, same greedy.
video-stitching: minimum clips to cover a time range; same greedy in another disguise.

The "BFS-on-an-interval-graph collapses to a two-pointer greedy" pattern is one of the highest-frequency interview tricks; this article is the canonical drill.

How parikshan turns this into a learning loop

This problem is the bridge from "1-D DP" to "BFS / greedy in 1-D DP's clothing". Treat it as such.

Read this article, then draw the layers for [2, 3, 1, 1, 4] on paper. The interval picture is the algorithm.
Practice mode with no AI: code the O(n²) DP first; submit. Then code the greedy; submit. Diff the timings. The greedy is roughly 100x faster on the bank's stress tests.
AI training: Explain. Ask the assistant why the greedy works. The right answer mentions "BFS layers are contiguous intervals". Anything vaguer is hand-waving; do not trust the rest of its DP / greedy analyses.
AI training: Optimise. Paste the DP into the assistant and ask for an O(n) version. The good response collapses to two pointers; a bad response just adds early termination.
Exam mode: redo cold. The bank's adversarial test includes [1] (singleton, expect 0), [2, 0, 2, 0, 1] (zeros mid-array but reachable), and [100000, 1, 1, ..., 1] (one giant first jump, expect 1).

In the AI-integrated workspace

Common AI failures on this problem:

Producing the O(n²) DP and calling it done: passes all sample tests, TLEs at n = 10⁵. Production-grade dispatch failure.
Producing real BFS with a queue of indices: works correctly but allocates and pushes / pops, ~20x slower than the two-pointer greedy, and uses O(n) memory. Acceptable but wasteful.
Off-by-one on the loop bound: loops over range(n) instead of range(n-1), counting one extra jump on inputs like [2, 1] (expected 1, returns 2).
The "commit on max" bug: agents sometimes write if farthest > cur_end: jumps += 1; cur_end = farthest (without i == cur_end), committing a jump every time the reach extends. This wildly overcounts jumps.

The 2027 engineer's discipline:

Recognise the shape: "minimum number of hops" on a 1-D array with bounded fan-out is the two-pointer greedy. Always.
State the algorithm in English before generating code: "maintain cur_end and farthest. Scan left to right. At each i, update farthest. When i == cur_end, commit one jump and advance cur_end = farthest. Stop when you cover the destination."
Verify on [2, 3, 1, 1, 4]. The answer must be 2. Off-by-one bugs surface immediately.
Verify on [1]. The answer must be 0. Singleton-handling bugs surface here.
Demand the O(1)-space form. If the agent produces a queue-based BFS, ask it to collapse the BFS into two integers. If it cannot do that transformation, the recurrence is not solid in its head; treat the output sceptically.

The candidate who calls out "BFS layers, two pointers, O(n)" within the first few seconds is the one who directs AI to a correct, linear, ten-line solution. Without that recognition, you end up reviewing 60 lines of generated BFS-with-queue and approving it because the samples pass.