### Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/jump-game-iii/

**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 * 10^4
- 0 <= arr[i] < arr.length
- 0 <= start < arr.length
```

### Explanation

The problem is an extended version of Jump Game and Jump Game II. We can solve this using BFS or DFS approach.

In this post, we will explore the BFS way.

#### BFS way

We will push the starting position into a queue and start exploring its neighbours. We need to maintain a boolean array to mark the nodes we visited.

Let's check the algorithm first:

```
// canReach(arr, start)
- set n = arr.size()
queue q = [start]
int visited[n]
int node
- loop while !q.empty()
node = q.start()
q.pop()
if arr[node] == 0
return true
if visited[node]
continue
if node - arr[node] >= 0
q.push(node - arr[node])
if node + arr[node] < 4
q.push(node + arr[node])
visited[node] = true
- while end
- return false
```

The time complexity of the above approach is **O(N)**, and the space complexity is

**O(n)**.

Let's check our solutions in **C++**, **Golang**, and **Javascript**.

#### C++ solution

```
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
queue<int> q{{start}};
int node;
vector<bool> visited(n);
while(!q.empty()) {
node = q.front();
q.pop();
if(arr[node] == 0) {
return true;
}
if(visited[node]) {
continue;
}
if(node - arr[node] >= 0) {
q.push(node - arr[node]);
}
if(node + arr[node] < n) {
q.push(node + arr[node]);
}
visited[node] = true;
}
return false;
}
};
```

#### Golang solution

```
func canReach(arr []int, start int) bool {
n := len(arr)
queue := []int{start}
visited := make([]bool, n)
for len(queue) != 0 {
node := queue[0]
queue = queue[1:]
if arr[node] == 0 {
return true
}
if visited[node] {
continue
}
if node - arr[node] >= 0 {
queue = append(queue, node - arr[node])
}
if node + arr[node] < n {
queue = append(queue, node + arr[node])
}
visited[node] = true
}
return false
}
```

#### Javascript solution

```
var canReach = function(arr, start) {
let n = arr.length;
let queue = [start];
let visited = [];
let node;
while(queue.length > 0) {
node = queue[0];
queue.shift();
if(arr[node] == 0) {
return true;
}
if(visited[node]) {
continue;
}
if(node - arr[node] >= 0) {
queue.push(node - arr[node]);
}
if(node + arr[node] < n) {
queue.push(node + arr[node]);
}
visited[node] = true;
}
return false;
};
```

Let's dry run our algorithm for a given input.

```
Input: arr = [4, 2, 3, 0, 3, 1, 2]
start = 5
Step 1: n = arr.size()
= 7
queue<int> q{{start}}
q = [5]
int node
vector<bool> visited(n)
Step 2: loop while !q.empty()
q = [5]
true
node = q.front()
= 5
q.pop()
q = []
if arr[node] == 0
arr[5] == 0
1 == 0
false
if visited[node]
visited[5]
false
if node - arr[node] >= 0
5 - arr[5] >= 0
5 - 1 >= 0
4 >= 0
true
q.push(node - arr[node])
q.push(4)
q = [4]
if node + arr[node] < n
5 + arr[5] < 7
5 + 1 < 7
6 < 7
true
q.push(node + arr[node])
q.push(6)
q = [4, 6]
visited[node] = true
visited[5] = true
Step 3: loop while !q.empty()
q = [4, 6]
true
node = q.front()
= 4
q.pop()
q = [6]
if arr[node] == 0
arr[4] == 0
3 == 0
false
if visited[node]
visited[4]
false
if node - arr[node] >= 0
4 - arr[4] >= 0
4 - 3 >= 0
1 >= 0
true
q.push(node - arr[node])
q.push(1)
q = [6, 1]
if node + arr[node] < n
4 + arr[4] < 7
4 + 3 < 7
7 < 7
false
visited[node] = true
visited[4] = true
Step 4: loop while !q.empty()
q = [6, 1]
true
node = q.front()
= 6
q.pop()
q = [1]
if arr[node] == 0
arr[6] == 0
2 == 0
false
if visited[node]
visited[6]
false
if node - arr[node] >= 0
6 - arr[6] >= 0
6 - 2 >= 0
4 >= 0
true
q.push(node - arr[node])
q.push(4)
q = [1, 4]
if node + arr[node] < n
6 + arr[6] < 7
6 + 2 < 7
8 < 7
false
visited[node] = true
visited[6] = true
Step 5: loop while !q.empty()
q = [1, 4]
true
node = q.front()
= 1
q.pop()
q = [4]
if arr[node] == 0
arr[1] == 0
2 == 0
false
if visited[node]
visited[1]
false
if node - arr[node] >= 0
1 - arr[1] >= 0
1 - 2 >= 0
-1 >= 0
false
if node + arr[node] < n
1 + arr[1] < 7
1 + 2 < 7
3 < 7
true
q.push(node + arr[node])
q.push(3)
q = [4, 3]
visited[node] = true
visited[1] = true
Step 6: loop while !q.empty()
q = [4, 3]
true
node = q.front()
= 4
q.pop()
q = [3]
if arr[node] == 0
arr[4] == 0
0 == 0
true
return true
We return the answer as true.
```

## Top comments (0)