Jump Game II

Difficulty: Medium Source: NeetCode

Problem

Given an integer array nums, you start at index 0. Each element nums[i] is your maximum jump length from that position. Return the minimum number of jumps to reach the last index. It is guaranteed you can reach the last index.

Example 1: Input: nums = [2, 3, 1, 1, 4] Output: 2 Explanation: Jump 2 → 3, then 3 → last.

Example 2: Input: nums = [2, 3, 0, 1, 4] Output: 2

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• The answer is guaranteed to exist.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Jump Game I — can you reach the end?
• BFS level-by-level — each “level” corresponds to one jump
• Greedy interval tracking — deciding when to commit to a jump

1. Brute Force / BFS

Intuition

Model each index as a node. From index i, you can jump to any index in [i+1, i+nums[i]]. Do a BFS starting from 0. The BFS level when we first reach n-1 is the minimum jumps.

Algorithm

1. BFS from index 0.
2. For each index in the current level, add all reachable indices to the next level.
3. Count levels until we reach n-1.

Solution

from collections import deque

def jump(nums):
    n = len(nums)
    if n == 1:
        return 0

    visited = {0}
    queue = deque([0])
    jumps = 0

    while queue:
        jumps += 1
        for _ in range(len(queue)):
            i = queue.popleft()
            for j in range(i + 1, min(i + nums[i] + 1, n)):
                if j == n - 1:
                    return jumps
                if j not in visited:
                    visited.add(j)
                    queue.append(j)

    return jumps


print(jump([2, 3, 1, 1, 4]))   # 2
print(jump([2, 3, 0, 1, 4]))   # 2
print(jump([1]))                # 0
print(jump([1, 2, 3]))         # 2

Complexity

• Time: O(n²) — each index visited and expanded
• Space: O(n)

2. Greedy — Implicit BFS with Current/Next Window

Intuition

Think of BFS level by level, but without an explicit queue. Each “level” is the range of indices reachable in exactly k jumps. Track two variables:

• cur_end: the farthest index reachable with the current number of jumps.
• farthest: the farthest index reachable with one more jump.

When we reach cur_end, we must make another jump — increment jump count and set cur_end = farthest. We never need to enumerate which index to jump to; we just need to know how far we can reach.

Algorithm

1. Initialise jumps = 0, cur_end = 0, farthest = 0.
2. For i from 0 to n-2 (don’t need to jump from the last index):
   • farthest = max(farthest, i + nums[i]).
   • If i == cur_end:
     • Increment jumps.
     • cur_end = farthest.
3. Return jumps.

Solution

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

    for i in range(n - 1):  # no jump needed from last index
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest

    return jumps


print(jump([2, 3, 1, 1, 4]))   # 2
print(jump([2, 3, 0, 1, 4]))   # 2
print(jump([1]))                # 0
print(jump([1, 2, 3]))         # 2
print(jump([0]))                # 0


# With annotations to show the "levels"
def jump_verbose(nums):
    n = len(nums)
    if n == 1:
        return 0

    jumps = 0
    cur_end = 0
    farthest = 0

    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest
            print(f"Jump {jumps}: can now reach index {cur_end}")

    return jumps


jump_verbose([2, 3, 1, 1, 4])

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Looping to n-1 instead of n-2. If we’re already at the last index, there’s no need to jump. The loop should go up to n-2. If your loop includes n-1, you might take an extra jump.

Incrementing jumps before checking farthest. Always update farthest before checking if we’ve hit cur_end. If you increment first, you might commit to a jump based on stale info.

Confusing this with Jump Game I. In Jump Game I we ask “can we reach the end?” In Jump Game II we ask “what’s the minimum jumps?” The greedy here is different — we track window boundaries, not just a max_reach.