Array Hopper II

Medium

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

Assumptions

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

Examples

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

• {2, 1, 1, 0, 2}, you are not able to reach the end of array, return -1 in this case.

Solution: Back to front scan. Memoized

At each index, check forward array[index] steps

set M[index] to lowest value + 1

public class Solution {
  // front to back
  // public int minJump(int[] array) {
  //   int length = array.length;
  //   int[] minJump = new int[length];
  //   minJump[0] = 0;
  //   for (int i = 1; i < length; i++){
  //     minJump[i] = -1;
  //     for (int j = i - 1; j >= 0; j--){
  //       if (j + array[j] >= i && minJump[j] != -1){
  //         if (minJump[i] == -1 || minJump[i] > minJump[j] + 1){
  //           minJump[i] = minJump[j] + 1;
  //         }
  //       }
  //     }
  //   }
  //   return minJump[length - 1];
  // }
  public int minJump(int[] array){
    int len = array.length;
    int[] M = new int[len];
    M[len - 1] = 0;
    for (int i = len - 2; i >= 0; i--){
      int maxJumps = array[i];
      int min = Integer.MAX_VALUE;
      for(int j = 1; j <= maxJumps; j++){
        if (i + j >= len) break;
        min = Math.min(min, M[i + j]);
      }
      M[i] = min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min + 1;
    }
    return M[0] == Integer.MAX_VALUE ? -1 : M[0];
  }
}

TC: O(N^2) double for loop

SC: O(N) Memoized