Jump Game II

Medium Problem 136 of 151 Java and Python

Problem

You start at index 0 of nums, where nums[i] is the maximum jump length from index i. Return the minimum number of jumps to reach the last index. The last index is always reachable.

Example 1

Input: nums = [2, 3, 1, 1, 4]
Output: 2
Why: Index 0 → 1 → 4.

Example 2

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

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000

Explanation

Think in rounds. With 0 jumps you can stand on index 0. With 1 jump you can reach a whole range of indexes. With 2 jumps, everything reachable from that range, and so on: a BFS where each level is a contiguous range.

Scan once, tracking the end of the current range and the farthest point reachable from it. When you pass the end of the range, you must take another jump.

Approach 1 · Naive

DP: fewest jumps to each index

Time O(n · max jump)
Space O(n)

jumps[j] = min(jumps[i] + 1) over every i that can reach j.

jumps[0] = 0, others infinity.
For each i, update every j in i + 1 … i + nums[i].
Return jumps[n - 1].

Java

import java.util.*;

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] jumps = new int[n];
        Arrays.fill(jumps, Integer.MAX_VALUE);
        jumps[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= Math.min(n - 1, i + nums[i]); j++) {
                jumps[j] = Math.min(jumps[j], jumps[i] + 1);
            }
        }
        return jumps[n - 1];
    }
}

Python

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumps = [0] + [float("inf")] * (n - 1)
        for i in range(n):
            for j in range(i + 1, min(n, i + nums[i] + 1)):
                jumps[j] = min(jumps[j], jumps[i] + 1)
        return jumps[-1]

Approach 2 · Optimal

Greedy ranges (implicit BFS)

Time O(n)
Space O(1)

Track end, the last index reachable with the current number of jumps, and farthest, the best reach seen so far. Reaching end means you must jump again.

jumps = 0, end = 0, farthest = 0.
For i from 0 to n – 2: farthest = max(farthest, i + nums[i]).
If i == end: jumps++, end = farthest.
Return jumps.

Java

class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int end = 0;
        int farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) {
                jumps++;
                end = farthest;
            }
        }
        return jumps;
    }
}

Python

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = end = farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == end:
                jumps += 1
                end = farthest
        return jumps

Complexity compared

Approach	Time	Space
Naive DP: fewest jumps to each index	O(n · max jump)	O(n)
Optimal Greedy ranges (implicit BFS)	O(n)	O(1)

Key takeaways

Stop the loop at n – 2: standing on the last index needs no further jump.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem