Minimum no. of Jumps to reach end of an array

The problem, simply

You get an array of non-negative numbers. You stand on index 0. The number on a spot is the longest hop you may take from it: from a spot holding 3 you may hop 1, 2 or 3 spots forward.

Give back the fewest hops needed to land on the last index. If you can never get there, give back -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Fill a table dp, where dp[i] is the fewest hops to land on i. The start costs 0 hops. For every other spot, look back at every earlier spot that can reach it.

1. dp[0] = 0, every other entry is "not reachable yet".
2. For each i from 1 to the end, for each j before i: if j is reachable and j + arr[j] >= i, then dp[i] = min(dp[i], dp[j] + 1).
3. Answer dp[n-1], or -1 if it is still not reachable.

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

How long it takes: every pair j < i is checked, O(n^2). Extra room: the table, O(n).

Way 2: the clever way

Think in rounds, like the frog. Keep three numbers:

• jumps: how many hops we have spent.
• end: the last index we can reach with jumps hops. The spots up to end are this round's window.
• far: the farthest index any spot in this window can reach.

Walk i from 0 to n - 2:

1. Update far = max(far, i + arr[i]).
2. If i == end, this round's window is used up, so spend a hop: jumps++, and the next window ends at end = far. If far did not move past i, you are stuck: return -1.
3. As soon as end reaches the last index, return jumps.

We never decide which exact stone to land on. We only track how far the next round can go. That is breadth first search over the stones, done with two numbers instead of a queue.

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0;                    // already on the last spot
        int jumps = 0, end = 0, far = 0;
        for (int i = 0; i < n - 1; i++) {
            far = Math.max(far, i + arr[i]);     // farthest the next round can go
            if (i == end) {                      // this round's window is used up
                if (far <= i) return -1;         // nothing reaches past here: stuck
                jumps++;
                end = far;
                if (end >= n - 1) return jumps;
            }
        }
        return -1;
    }
}

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

Watch out for

• A single element means 0 hops, even if it is 0.
• A 0 is only a problem if you are forced to land on it. Check for "stuck" with far <= i when a window runs out.
• Some versions promise the end is always reachable (LeetCode 45). Others want -1. Ask.

What interviewers ask next

• Can you reach the end at all (Jump Game I)? Keep only far. If i ever passes far, you are stuck.
• Print the route. In the table way, remember which j gave the best dp[i], then walk back from the end. In the greedy way, remember which spot set far in each round.
• Hops can go left or right by exactly arr[i] (Jump Game III). Then it is a real graph search: breadth first search with a queue and a visited set.
• Why is the greedy correct? It is breadth first search: the window is one level. Every spot in a window takes the same number of hops, and the next window is everything one more hop can reach.

Remember this

Grown-up words: the stones and hops are a directed graph, the rounds are breadth first search levels, the window end is the current level boundary, and the table way is 1D dynamic programming.