Jump Game II: Minimum Jumps with Greedy BFS

You are given a 0-indexed array of integers nums where nums[i] represents the maximum jump length from position i. You start at index 0. Return the minimum number of jumps to reach the last index. The problem guarantees you can always reach the end.

This is LeetCode 45: Jump Game II, a medium problem that builds directly on Jump Game (LeetCode 55). Instead of asking whether you can reach the end, it asks how few jumps it takes. The answer is a greedy algorithm that thinks in BFS levels without ever building a queue.

Why this problem matters

Jump Game II teaches you to recognize implicit BFS on an array. Each "jump" is really a BFS level: all indices reachable from the current level form the next level. By tracking two boundaries (the end of the current level and the farthest index discovered), you count levels, and each level is one jump.

This greedy-BFS pattern shows up whenever you need the minimum number of steps to cross an array or sequence. It also reinforces the farthest-reach tracking from Jump Game, extending it with a boundary variable that tells you when to increment your jump counter.

The brute force approach

The most natural starting point is BFS with a queue. From index 0, enqueue every index you can reach. From each of those, enqueue every index they can reach. Count levels until you hit the last index.

def jump_bfs(nums):
    from collections import deque
    n = len(nums)
    if n == 1:
        return 0
    visited = [False] * n
    visited[0] = True
    queue = deque([0])
    jumps = 0
    while queue:
        jumps += 1
        for _ in range(len(queue)):
            idx = queue.popleft()
            for next_idx in range(idx + 1, min(idx + nums[idx] + 1, n)):
                if next_idx == n - 1:
                    return jumps
                if not visited[next_idx]:
                    visited[next_idx] = True
                    queue.append(next_idx)
    return -1

This works, but it uses O(n) space for the queue and visited array, and each index might be enqueued individually. In the worst case it visits O(n^2) index pairs. You can do much better.

The key insight: greedy range expansion

You do not need an explicit queue because BFS levels on a contiguous array are always contiguous ranges. If level k covers indices [a, b], then level k + 1 covers [b + 1, farthest] where farthest is the maximum of i + nums[i] for all i in [a, b].

Two variables are enough to track these ranges:

• end: the last index of the current jump's range (the right edge of the current BFS level)
• farthest: the farthest index reachable from any position in the current level

As you scan left to right, update farthest = max(farthest, i + nums[i]) at each index. When i reaches end, one jump is complete. Set end = farthest and increment the jump counter. If end reaches or passes the last index, you are done.

Walking through it step by step

Let's trace through nums = [2, 3, 1, 1, 4]. The dashed orange line marks the current boundary (end). Green cells are within reach. The blue cell is the current index.

The algorithm makes exactly 2 jumps. At no point did it need a queue or visited array. It just tracked where the current level ends and how far the next level reaches.

The greedy solution

def jump(nums):
    n = len(nums)
    jumps = 0
    end = 0
    farthest = 0

    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:
            jumps += 1
            end = farthest

    return jumps

Here is what each piece does:

1. farthest = max(farthest, i + nums[i]): from index i, you can reach up to i + nums[i]. Keep the best reach seen so far.
2. if i == end: you have scanned every index in the current jump's range. Time to take the next jump.
3. jumps += 1 and end = farthest: commit the jump. The next range now extends to farthest.
4. Loop runs to n - 1 (not n): you never need to "jump from" the last index, so the loop stops one step before it. This avoids counting an extra jump when end lands exactly on n - 1.

Complexity analysis

Time: O(n). One pass through the array. Each index is visited once, and each visit does O(1) work: one comparison, one max.

Space: O(1). Three integer variables: jumps, end, and farthest. No queue, no visited array, no recursion stack.

This matches the lower bound. You must inspect every element at least once because any element could shorten or lengthen the optimal path.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently:

1. Greedy range expansion

The pattern of maintaining a "current window" and a "next window" as you scan forward, then swapping them at the boundary:

end = 0
farthest = 0
for i in range(n - 1):
    farthest = max(farthest, reach(i))
    if i == end:
        end = farthest
        count += 1

You see this whenever BFS levels map to contiguous ranges. The same skeleton appears in problems where you expand a reachable zone one level at a time: word ladder on arrays, minimum operations to sort, and other "minimum steps" problems on sequences.

2. Implicit BFS levels

Standard BFS uses a queue and processes one level at a time by remembering the queue size at the start of each level. When the search space is a contiguous range (like array indices), you can replace the queue with two pointers (the start and end of the current level). This drops memory from O(n) to O(1) while preserving the level-by-level structure.

The key recognition step is noticing that your "neighbors" from any index in the current level form a contiguous block. Once you see that, the queue becomes unnecessary overhead.

Edge cases

Before submitting, verify these:

• Array of length 1 [0]: you are already at the last index. The loop range(0) runs zero iterations. Return 0.
• Already at the end [5]: same as above. Length 1 means zero jumps.
• All ones [1, 1, 1, 1]: every jump advances exactly one index. The answer is n - 1 (here, 3). The algorithm hits i == end at every step, incrementing jumps each time.
• Large first element [10, 0, 0, 0, 1]: one jump covers the entire array. farthest = 10 after index 0, i == end fires at i = 0, sets end = 10. The loop ends and returns 1.
• Two elements [1, 0]: one jump from index 0 to index 1. At i = 0, farthest = 1, i == end fires, jumps = 1. Loop ends.

The greedy approach handles all of these without special-case logic.

Common mistakes

1. Looping through all n indices. If you iterate range(n) instead of range(n - 1), you will count an extra jump when end lands on the last index. The off-by-one silently passes some test cases but fails others.

2. Checking farthest after the boundary update. Some people add an early exit if farthest >= n - 1: return jumps inside the i == end block. This works, but placing it incorrectly (before incrementing jumps) gives an answer that is one too low.

3. Confusing this with Jump Game I. Jump Game I asks a boolean question: can you reach the end? Jump Game II asks for the minimum count. Reusing the Jump Game I code and trying to bolt on a counter does not work because Jump Game I does not track level boundaries.

4. Forgetting that the problem guarantees reachability. Because you can always reach the end, you never need to handle the "impossible" case. This simplifies the code but can cause confusion if you are used to returning -1 from BFS.

From understanding to recall

The greedy BFS solution is six lines of logic: initialize three variables, scan with one max update, and increment jumps at the boundary. Clean and short. But can you reproduce it from memory under interview pressure?

The details trip people up: looping to n - 1 instead of n, updating farthest before checking the boundary, setting end = farthest after incrementing jumps. These are small choices that matter, and they are easy to second-guess if you have not practiced writing them from scratch.

Spaced repetition locks these details in. You write the greedy-BFS loop from memory at increasing intervals. After a few rounds, the boundary-tracking pattern is automatic. You see "minimum number of jumps" and the code flows out without hesitation.

The two building blocks here, greedy range expansion and implicit BFS levels, appear across dozens of LeetCode problems. Learning them independently and drilling them with spaced repetition is far more effective than re-solving Jump Game II from scratch every time.

Related posts

• Jump Game - The prerequisite problem using greedy farthest-reach tracking (boolean version)
• Gas Station - Another greedy one-pass problem with a reset boundary

CodeBricks breaks Jump Game II into its greedy-range-expansion and implicit-BFS-level building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a "minimum steps" problem shows up in your interview, you do not think about it. You just write it.