> 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/bfs/array-hopper-iv.md).

# Array Hopper IV

Hard

Given an array A of non-negative integers, you are initially positioned at an arbitrary index of the array. **A\[i] means the maximum jump distance from that position (you can either jump left or jump right).** Determine the minimum jumps you need to reach the right end of the array. Return -1 if you can not reach the right end of the array.

**Assumptions**

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

**Examples**

* {1, 3, 1, 2, 2}, if the initial position is 2, the minimum jumps needed is 2 (jump to index 1 then to the right end of array)
* {3, 3, 1, 0, 0}, if the initial position is 2, the minimum jumps needed is 2 (jump to index 1 then to the right end of array)
* {4, 0, 1, 0, 0}, if the initial position is 2, you are not able to reach the right end of array, return -1 in this case.

**Solution:** BFS starting at index

```java
public class Solution {
  public int minJump(int[] array, int index) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> hashset = new HashSet<>();
    queue.offer(index);
    hashset.add(index);
    int count = 0;
    while (!queue.isEmpty()) {
      int size = queue.size();
      for (int j = 0; j < size; j++) {
        int cur = queue.poll();
        if (cur == array.length - 1) {
          return count;
        }
        for (int i = 1; i <= array[cur]; i++) {
          if (cur + i < array.length && !hashset.contains(cur + i)) {
            queue.offer(cur + i);
            hashset.add(cur + i);
          }
          if (cur - i >= 0 && !hashset.contains(cur - i)) {
            queue.offer(cur - i);
            hashset.add(cur - i);
          }
        }
      }
      count++;

    }
    return -1;
  }
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(N) HashSet