LeetCode #45 Medium

Jump Game II

Given that you can always reach the last index, return the minimum number of jumps needed.

greedyarraybfs

02

Intuition

The instinct is to add a jump every time you move, but jumps are not per index — they are per band. Every index reachable in one jump forms a contiguous stretch; everything reachable in two forms the next. So this is breadth-first search on levels with no queue: sweep the current band noting the furthest it reaches, and only when you fall off its right edge does the count go up by one.

How to spot this pattern

A BFS over levels, flattened into one pass. curEnd is the boundary of the current jump's reach; when the scan hits it, a jump must be spent and the boundary moves to farthest. Counting level transitions is the same idea as BFS depth, without the queue.

03

Approach

1

Why the bands are contiguous

From a band of indices you may jump any distance up to each element's value, so the union of everything they reach is an unbroken stretch. That is what makes this a level-order traversal in disguise: the set of indices at BFS depth j is always an interval, so it needs two numbers rather than a queue.

2

Sweep with three counters

Keep curEnd (the right edge of the band you are in), farthest (the furthest index anything in this band reaches), and jumps. For each i, update farthest = max(farthest, i + nums[i]). This is the same reach calculation as Jump Game I, used to build the next level rather than to test feasibility.

3

Count a jump when the band ends

When i == curEnd the band is exhausted, so going further costs one more jump: increment jumps and set curEnd = farthest. Now the off-by-one that catches almost everyone — loop only to n - 2. Arriving at the last index is the goal, so if the final index happens to close a band, looping to n - 1 counts a phantom jump you never needed to take. O(n) time, O(1) space, against O(n^2) for the DP.

04

Solution & live demo

▶1class Solution:
▶2    def jump(self, nums):
▶3        jumps = curEnd = farthest = 0
▶4        for i in range(len(nums) - 1):
▶5            farthest = max(farthest, i + nums[i])
▶6            if i == curEnd:
▶7                jumps += 1
▶8                curEnd = farthest
▶9                if curEnd >= len(nums) - 1:
▶10                    break
▶11        return jumps

05

Common pitfalls

Looping to the last index

✗ Wrong

for i in range(len(nums)):

✓ Right

for i in range(len(nums) - 1):

Standing on the final index means you've arrived; scanning it can trigger one more i == curEnd bump and return a count one too high. Excluding it makes the boundary logic exact.

Incrementing on every extension

✗ Wrong

if farthest > curEnd:
    jumps += 1

✓ Right

if i == curEnd:
    jumps += 1
    curEnd = farthest

A jump is spent only when the current reach is exhausted, not whenever a better landing appears. Counting extensions massively overcounts on arrays with large steps.

Greedily taking the largest single step

✗ Wrong

i += nums[i]  # always jump as far as possible

✓ Right

farthest = max(farthest, i + nums[i])

The longest jump can land somewhere with poor onward reach — on [3, 1, 1, 1, 4] jumping to index 3 is worse than to index 1. The right greedy choice is the furthest reachable frontier over the whole level, not the biggest individual step.

06

Edge cases

Single element array

The loop never runs and 0 is returned — you are already there.

Two elements

One jump, provided nums[0] >= 1, which the problem guarantees.

Large first jump covering the array

curEnd immediately covers the end, so the answer is 1.

Looping to n-1 instead of n-2

The classic off-by-one: it counts a phantom extra jump when the last index closes a band. Stopping at n - 2 avoids it.

07

Complexity

Time

O(n)

Space

O(1)

A BFS over levels where each level is an interval, so no queue is needed.