Minimum number of jumps to reach end

The problem, simply

You get a list of non-negative numbers. You stand on square 0. The number on a square is the longest jump you may make from it: from a square with 3 you may jump 1, 2 or 3 squares forward.

Give back the fewest jumps needed to land on the last square. If you can never get there, give back -1. If the list has one square, you are already there: 0 jumps.

A story to remember it

Picture it

Examples

Way 1: the simple way

From the square you stand on, try every allowed jump length and ask the same question from where you land.

1. If you stand on the last square, 0 more jumps.
2. Otherwise, for each jump k from 1 to a[i], ask fewest(i + k).
3. The answer is 1 plus the smallest of those that are possible.

class Solution {
    public int minJumps(int[] a) {
        int best = fewest(a, 0);
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    private int fewest(int[] a, int i) {
        if (i >= a.length - 1) return 0;                   // on the last square
        int best = Integer.MAX_VALUE;                      // means "cannot reach"
        for (int k = 1; k <= a[i] && i + k < a.length; k++) {
            int rest = fewest(a, i + k);
            if (rest != Integer.MAX_VALUE) best = Math.min(best, 1 + rest);
        }
        return best;
    }
}

How long it takes: the same squares are solved again and again, up to O(2^n) calls. Extra room: the waiting calls, O(n).

Way 2: the clever way

Count the ripple rings.

1. end is the last square the current ring covers. far is the farthest any square seen so far can reach. jumps counts rings.
2. Walk i from 0 to n - 2. Update far = max(far, i + a[i]).
3. When i reaches end, the ring is used up, so we must jump: jumps++ and end = far. If far did not move past i, we are stuck: return -1.
4. Stop as soon as end covers the last square.

The bracket is the current ring. far points to the edge of the next ring.

class Solution {
    public int minJumps(int[] a) {
        int n = a.length;
        if (n <= 1) return 0;                    // already on the last square
        int jumps = 0, end = 0, far = 0;
        for (int i = 0; i < n - 1; i++) {
            far = Math.max(far, i + a[i]);       // farthest the next ring reaches
            if (i == end) {                      // the current ring is used up
                if (far <= i) return -1;         // nobody in this ring moves us forward
                jumps++;
                end = far;
                if (end >= n - 1) return jumps;  // the new ring covers the end
            }
        }
        return -1;
    }
}

How long it takes: one walk, O(n). Extra room: three numbers, O(1).

Another way: the DP table

dp[i] is the fewest jumps to land on square i. dp[0] = 0, and dp[i] is 1 plus the smallest dp[j] over squares j < i that can reach i (j + a[j] >= i).

import java.util.Arrays;

class Solution {
    public int minJumps(int[] a) {
        int n = a.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] != Integer.MAX_VALUE && j + a[j] >= i) {   // j can reach i
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }
}

This is O(n^2) time and O(n) room. It is slower, but it is the one to reach for when jumps have different costs, because then the rings trick no longer works.

Watch out for

• Loop only to n - 2. If you also process the last square when i == end, you count one extra jump.
• A single square needs 0 jumps, even if its number is 0.
• In the recursion, adding 1 to Integer.MAX_VALUE overflows. Check before adding.

What interviewers ask next

• Can you only ask if the end is reachable (Jump Game I)? Keep far, and fail if some i > far.
• Print the jump path. While scanning a ring, remember which square gave the new far. Those squares are the launch pads.
• What if you can jump forward or backward by exactly a[i] (Jump Game III)? It becomes a graph search: breadth first search from the start.
• Why is the greedy right? It is breadth first search on squares, where each ring is one level. Breadth first search always finds the fewest steps.

Remember this

Grown-up words: the rings are BFS levels, the farthest reach is the frontier of the next level, the table version is a 1D DP over positions, and the repeated fewest(i) calls are overlapping subproblems.