Problem Explanation

We are given an array of non-negative integers and a start index. At any index i we can either move forward by arr[i] or move backward by arr[i]. We need to return a boolean indicating if we can reach at any 0 in the array or not. It is important to notice that the jumps should always leave the current index inside the array boundaries, i.e. 0 <= i < arr.length.

Example

Let's take an example where we are given an array arr = [4,2,3,0,3,1,2] and a start index 5. We can reach index 3 which has a 0 value as shown below:

index 5 -> index 4 -> index 1 -> index 3

Therefore, the output is True.

Solution Explanation

This problem can be solved using Breadth-First Search (BFS) algorithm. We can add the start index to a queue and start a loop that will continue till the queue is not empty. Inside the loop, we "visit" the node (index) at the front of the queue, and if the array value at the node is 0, we return True as we have reached our goal. We then check for the next nodes to be visited if this node does not have 0. These nodes will be at the indices node + arr[node] and node - arr[node], provided the indices lie within valid boundaries. We also maintain a seen array to prevent cycles and revisiting nodes in the queue.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  bool canReach(vector<int>& arr, int start) {
6    const int n = arr.size();      // getting size of array
7    queue<int> q{{start}};         // initializing queue with start index
8    vector<bool> seen(n);          // boolean vector to track visited nodes
9
10    while (!q.empty()) {           // continue while the queue is not empty
11      const int node = q.front();  
12      q.pop();
13
14      if (arr[node] == 0)          // if current node value is 0, return True
15        return true;
16      if (seen[node])              // if current node is already visited, continue to next iteration
17        continue;
18
19      // Check available next steps
20      if (node - arr[node] >= 0)   // if valid, add (node - arr[node]) to queue
21        q.push(node - arr[node]);
22      if (node + arr[node] < n)    // if valid, add (node + arr[node]) to queue
23        q.push(node + arr[node]);
24
25      seen[node] = true;           // mark current node as visited 
26    }
27
28    return false;  // return false if the queue becomes empty and no 0 found
29  }
30};

Java Solution

1
2java
3class Solution {
4    public boolean canReach(int[] arr, int start) {
5        int n = arr.length;        
6        Queue<Integer> q = new LinkedList<>();
7        q.add(start);   
8        boolean[] seen = new boolean[n];
9
10        while (!q.isEmpty()) {
11            int node = q.poll();
12
13            if (arr[node] == 0)
14                return true;
15            if (seen[node])
16                continue;
17
18            if (node - arr[node] >= 0)
19                q.add(node - arr[node]);
20            if (node + arr[node] < n)
21                q.add(node + arr[node]);
22
23            seen[node] = true;
24        }
25
26        return false;
27    }
28}

Python Solution

1
2python
3class Solution:
4    def canReach(self, arr: List[int], start: int) -> bool:
5        n = len(arr)
6        q = [start]
7        seen = [False]*n
8
9        while q:
10            node = q.pop(0)
11
12            if arr[node] == 0:
13                return True
14            if seen[node]:
15                continue
16
17            if node - arr[node] >= 0:
18                q.append(node - arr[node])
19            if node + arr[node] < n:
20                q.append(node + arr[node])
21
22            seen[node] = True
23
24        return False

JavaScript Solution

1
2javascript
3var canReach = function(arr, start) {
4    const n = arr.length;
5    const queue = [start];
6    const seen = Array(n).fill(false);
7
8    while(queue.length > 0) {
9        const node = queue.shift();
10
11        if(arr[node] === 0) {
12            return true;
13        }
14        if(seen[node]) {
15            continue;
16        }
17
18        if(node - arr[node] >= 0) {
19            queue.push(node - arr[node]);
20        }
21        if(node + arr[node] < n) {
22            queue.push(node + arr[node]);
23        }
24
25        seen[node] = true;
26    }
27
28    return false;
29};

C# Solution

1
2csharp
3public class Solution {
4    public bool CanReach(int[] arr, int start) {
5        int n = arr.Length;
6        Queue<int> queue = new Queue<int>();
7        queue.Enqueue(start);
8        bool[] visited = new bool[n];
9
10        while(queue.Count > 0) {
11            int node = queue.Dequeue();
12
13            if(arr[node] == 0) {
14                return true;
15            }
16            if(visited[node]) {
17                continue;
18            }
19            
20            if(node - arr[node] >= 0) {
21                queue.Enqueue(node - arr[node]);
22            }
23            if(node + arr[node] < n) {
24                queue.Enqueue(node + arr[node]);
25            }
26
27            visited[node] = true;
28        }
29
30        return false;
31    }
32}

In all solutions so far, the depth-first or breadth-first searches are begun from the starting point and then all possible directions are added to the agenda, visited points are marked and the search continues until an index with 0 is found or if there are no new places to explore (if the queue is empty).

Breadth-first search starts traversing from the root node and visits nodes in a level by level manner. Each neighboring node is visited first before moving onto the next level nodes. In this problem, neighbors of a node come from steps forward or backward.

The main point here is to handle the constraints carefully. The step size is given by the current node and we have to make sure not to jump out of bounds as well as handle the issue that comes from cycles. Valid steps should be within the array bounds and hence, checking whether a position is valid simply requires a bounds check 0 <= i < arr.length.

The time complexity of this algorithm is O(n), where n is the size of the input array. This is because in the worst case, we might have to process each element of the array once.

The space complexity is also O(n) as in the worst case we might have to add each element to the queue and also maintain its 'visited' state. Hence, space complexity is also linear.

Overall, this problem not only tests your basic understanding of traversal algorithms and some standard data structures but also tests your ability in dealing with constraints and corner cases.

Always keep in mind to first confirm the problem constraints (array bounds in this case) and also consider how to handle cyclical cases (using a visited array in this case) when dealing with any graph or array problems. Keep practicing and happy coding!