Array Hopper III

Medium

Given an array of non-negative integers, you are initially positioned at index 0 of the array. A[i] means the maximum jump distance from that position (you can only jump towards the end of the array). Determine the minimum number of jumps you need to jump out of the array.

By jump out, it means you can not stay at the end of the array. Return -1 if you can not do so.

Assumptions

• The given array is not null and has length of at least 1.

Examples

• {1, 3, 2, 0, 2}, the minimum number of jumps needed is 3 (jump to index 1 then to the end of array, then jump out)

• {3, 2, 1, 1, 0}, you are not able to jump out of array, return -1 in this case.

Solution: Back to front scan. Memoized

Scan from n - 1 to 0 index

At each index, check array[index] steps forward.

Set M[index] to lowest jump amount + 1

public class Solution {
  public int minJump(int[] array) {
    // let N be length of input array
    int n = array.length;

    // create N length memoization array
    int[] m = new int[n];

    // walk backwards 
    for (int i = n - 1; i >= 0; i--) {
      int maxJumps = array[i];

      // base case
      if (maxJumps + i >= m.length) {
        m[i] = 1;
        continue;
      }

      // inductive step
      int bestJump = Integer.MAX_VALUE;
      for (int j = i; j <= i + maxJumps; j++) {
        if (m[j] > 0) {
          // found a path to the end
          bestJump = Math.min(bestJump, m[j] + 1);
        }
      }

      // if we found a path to the end, update accordingly
      if (bestJump != Integer.MAX_VALUE) {
        m[i] = bestJump;
      }
    }

    return m[0] == 0 ? -1 : m[0];
  }
}