# 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];
  }
}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dynamic-programming/array-hopper-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.