> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dynamic-programming/array-hopper-iii.md).

# 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

```java
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];
  }
}

```