# 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

```java
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