# 1306. Jump Game III (M)

Given an array of non-negative integers `arr`, you are initially positioned at `start` index of the array. When you are at index `i`, you can jump to `i + arr[i]` or `i - arr[i]`, check if you can reach to **any** index with value 0.

Notice that you can not jump outside of the array at any time.

 

**Example 1:**

```
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 
```

**Example 2:**

```
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3
```

**Example 3:**

```
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.
```

 

**Constraints:**

* `1 <= arr.length <= 5 * 104`
* `0 <= arr[i] < arr.length`
* `0 <= start < arr.length`

### Solution:

Version 1: BFS

```
class Solution {
    public boolean canReach(int[] arr, int start) {
        
        if(arr[start] == 0) return true;
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] visited = new boolean[arr.length];
        
        queue.offer(start);
        visited[start] = true;
        
        while(!queue.isEmpty())
        {
            int currentIndex = queue.poll();
            if(arr[currentIndex] == 0)
            {
                return true;
            }
            
            int dir1 = currentIndex + arr[currentIndex];
            int dir2 = currentIndex - arr[currentIndex];
            
            if(dir1 < arr.length && !visited[dir1])
            {
                queue.offer(dir1);
                visited[dir1] = true;
            }
            if(dir2 >= 0 && !visited[dir2])
            {
                queue.offer(dir2);
                visited[dir2] = true;
            }
        }

        return false;         
    }
}
```


---

# 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://junnie.gitbook.io/nine-chapter/3.breadth-first-search/1306.-jump-game-iii-m.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.