MediumBlind75ArrayDPGreedy

Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index. Each element represents the maximum jump length. Return the minimum number of jumps to reach the last index.

Examples

Input
nums = [2,3,1,1,4]
Output
2

The minimum number of jumps to reach the last index is 2 (jump 1 step from index 0 to 1, then 3 steps to the last index).

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

The minimum number of jumps to reach the last index is 2.

Constraints

  • •1 <= nums.length <= 10^4
  • •0 <= nums[i] <= 1000

Approaches

Use BFS to find the minimum jumps (shortest path).

CodeT: O(n^2) | S: O(n)
from collections import deque

def jump(nums):
    n = len(nums)
    if n <= 1:
        return 0
    queue = deque([(0, 0)])
    visited = {0}
    while queue:
        pos, jumps = queue.popleft()
        for i in range(1, nums[pos] + 1):
            next_pos = pos + i
            if next_pos >= n - 1:
                return jumps + 1
            if next_pos not in visited:
                visited.add(next_pos)
                queue.append((next_pos, jumps + 1))
    return -1

Use DP where dp[i] is the minimum jumps to reach index i.

CodeT: O(n^2) | S: O(n)
def jump(nums):
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(1, n):
        for j in range(i):
            if dp[j] != float('inf') and j + nums[j] >= i:
                dp[i] = min(dp[i], dp[j] + 1)
    return dp[-1]

Track the current end of the jump range and the farthest reachable.

Diagram

nums = [2,3,1,1,4] i=0: farthest=2, i==0=jumps=1, current_end=2 i=1: farthest=max(2,4)=4 i=2: farthest=max(4,3)=4, i==2=jumps=2, current_end=4 Result: 2
CodeT: O(n) | S: O(1)
def jump(nums):
    n = len(nums)
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

Complexity Comparison

BFS
T: O(n^2)S: O(n)

Use BFS to find the minimum jumps (shortest path).

DP - Bottom Up
T: O(n^2)S: O(n)

Use DP where dp[i] is the minimum jumps to reach index i.

Greedy
T: O(n)S: O(1)

Track the current end of the jump range and the farthest reachable.

Common Mistakes

Using BFS when greedy is more efficient

Not handling the edge case of a single element

Using O(n) space when O(1) is possible

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems