  # LeetCode - Jump Game III

## 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 neighbors. 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
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;
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 = 

int node
vector<bool> visited(n)

Step 2: loop while !q.empty()
q = 
true

node = q.front()
= 5

q.pop()
q = []

if arr[node] == 0
arr == 0
1 == 0
false

if visited[node]
visited
false

if node - arr[node] >= 0
5 - arr >= 0
5 - 1 >= 0
4 >= 0
true

q.push(node - arr[node])
q.push(4)

q = 

if node + arr[node] < n
5 + arr < 7
5 + 1 < 7
6 < 7
true

q.push(node + arr[node])
q.push(6)

q = [4, 6]

visited[node] = true
visited = true

Step 3: loop while !q.empty()
q = [4, 6]
true

node = q.front()
= 4

q.pop()
q = 

if arr[node] == 0
arr == 0
3 == 0
false

if visited[node]
visited
false

if node - arr[node] >= 0
4 - arr >= 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 < 7
4 + 3 < 7
7 < 7
false

visited[node] = true
visited = true

Step 4: loop while !q.empty()
q = [6, 1]
true

node = q.front()
= 6

q.pop()
q = 

if arr[node] == 0
arr == 0
2 == 0
false

if visited[node]
visited
false

if node - arr[node] >= 0
6 - arr >= 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 < 7
6 + 2 < 7
8 < 7
false

visited[node] = true
visited = true

Step 5: loop while !q.empty()
q = [1, 4]
true

node = q.front()
= 1

q.pop()
q = 

if arr[node] == 0
arr == 0
2 == 0
false

if visited[node]
visited
false

if node - arr[node] >= 0
1 - arr >= 0
1 - 2 >= 0
-1 >= 0
false

if node + arr[node] < n
1 + arr < 7
1 + 2 < 7
3 < 7
true

q.push(node + arr[node])
q.push(3)

q = [4, 3]

visited[node] = true
visited = true

Step 6: loop while !q.empty()
q = [4, 3]
true

node = q.front()
= 4

q.pop()
q = 

if arr[node] == 0
arr == 0
0 == 0
true

return true

We return the answer as true.
``````