Minimum Number of Jumps to Reach the End

Given an array of non-negative integers where nums[i] is the maximum jump length from index i, start at index 0 and return the minimum number of jumps needed to reach the last index, or OptionalInt.empty() if it can't be reached. OptionalInt is a container that holds either one int or nothing.

LeetCode: 45. Jump Game II

Example

Text

[2, 3, 1, 1, 4]                      ->  2       (0 -> 1 -> 4)
[1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]    ->  3       (0 -> 1 -> 3 -> 10)
[3, 2, 1, 0, 4]                      ->  empty   (every path gets stuck at index 3)

Brute force: a DP table

Let jumps[i] be the fewest jumps to reach index i. Index i can be reached from any earlier j with j + nums[j] >= i, so:

Text

jumps[0] = 0
jumps[i] = 1 + min(jumps[j]) over all j < i that can reach i

(A plain recursion that tries every jump from every index is exponential; the table computes each index once.)

The table is an int[] where -1 marks an index that can't be reached yet.

Java

import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    static OptionalInt minJumps(int[] nums) {
        int n = nums.length;
        int[] jumps = new int[n];
        Arrays.fill(jumps, -1);
        jumps[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i && jumps[j] != -1) {
                    if (jumps[i] == -1 || jumps[j] + 1 < jumps[i]) jumps[i] = jumps[j] + 1;
                }
            }
        }
        return jumps[n - 1] == -1 ? OptionalInt.empty() : OptionalInt.of(jumps[n - 1]);
    }

    public static void main(String[] args) {
        System.out.println(minJumps(new int[]{2, 3, 1, 1, 4}) + " " + minJumps(new int[]{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}));
        System.out.println(minJumps(new int[]{3, 2, 1, 0, 4}));
    }
}

Output

OptionalInt[2] OptionalInt[3]
OptionalInt.empty

Time: O(n²). Space: O(n).

Optimal: greedy, one jump level at a time

Think of breadth-first search: the indices reachable with k jumps form a contiguous range, and the next range ends at the farthest index any of them can reach. Scan left to right, tracking:

end: the last index reachable with the current number of jumps,
farthest: the farthest index reachable with one more jump.

When the scan passes end, another jump is needed, and the new end is farthest. If farthest doesn't move past the current index, the end is unreachable.

i	0	1	2	3	4
nums[i]	2	3	1	1	4
farthest	2	4	4
jumps (after i)	1 (end = 2)	1	2 (end = 4), stop

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt minJumps(int[] nums) {
        int n = nums.length;
        int jumps = 0, end = 0, farthest = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) {
                if (farthest <= i) {
                    return OptionalInt.empty(); // stuck: nothing reaches past i
                }
                jumps++;
                end = farthest;
                if (end >= n - 1) break;
            }
        }
        return OptionalInt.of(jumps);
    }

    public static void main(String[] args) {
        System.out.println(minJumps(new int[]{2, 3, 1, 1, 4}) + " " + minJumps(new int[]{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}));
        System.out.println(minJumps(new int[]{3, 2, 1, 0, 4}));
        System.out.println(minJumps(new int[]{0}) + " " + minJumps(new int[]{0, 1}));
    }
}

Output

OptionalInt[2] OptionalInt[3]
OptionalInt.empty
OptionalInt[0] OptionalInt.empty

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

The loop stops at n - 2: once the last index is inside the current range, no further jump is needed.

Edge cases

Single element: already at the end, 0 jumps.
A zero that blocks every path: OptionalInt.empty(), detected when farthest stops at the current index.
Only reachability (LeetCode 55): track farthest alone and check that it never falls behind i.