Solution Explanation: Breadth-First Search (BFS)

This problem asks whether we can reach an index with a value of 0 starting from a given index in an array. The movement is constrained: from index i, we can jump to i + arr[i] or i - arr[i], provided these indices are within the array bounds.

The most efficient approach is Breadth-First Search (BFS). BFS explores the search space level by level, guaranteeing that we find the shortest path (if one exists) to a target (in this case, an index with value 0).

Algorithm:

1. Initialization:

   • Create a queue q and enqueue the start index.
   • Create a visited array (or modify the input array arr in-place) to keep track of visited indices. This prevents cycles and redundant explorations.

2. BFS Iteration:

   • While the queue is not empty:
     • Dequeue an index i from the queue.
     • If arr[i] == 0, we've reached our target, so return true.
     • Mark index i as visited (e.g., set arr[i] = -1, or visited[i] = true).
     • Calculate the possible next indices: next1 = i + arr[i] and next2 = i - arr[i].
     • Check if next1 and next2 are within the array bounds (0 <= next <= arr.length -1) and have not been visited. If they are valid and unvisited, enqueue them into the queue.

3. No Path Found:

   • If the queue becomes empty and we haven't found an index with value 0, it means no such path exists, so return false.

Time and Space Complexity:

• Time Complexity: O(N), where N is the length of the array. In the worst case, we might visit each index once.
• Space Complexity: O(N) in the worst case, due to the queue (which can hold up to all the indices) and the visited array (or the space used for modifying arr in-place).

Code Examples (with detailed comments):

Python:

from collections import deque
 
def canReach(arr, start):
    q = deque([start])  # Queue for BFS
    visited = [False] * len(arr)  # Array to track visited indices
 
    while q:
        i = q.popleft()
        if arr[i] == 0:  # Target found
            return True
        if visited[i]:  # Already visited this index
            continue
        visited[i] = True  # Mark as visited
 
        next1 = i + arr[i]
        next2 = i - arr[i]
 
        if 0 <= next1 < len(arr) and not visited[next1]:
            q.append(next1)
        if 0 <= next2 < len(arr) and not visited[next2]:
            q.append(next2)
 
    return False  # No path to index with value 0
 

Java:

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public boolean canReach(int[] arr, int start) {
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        boolean[] visited = new boolean[arr.length];
 
        while (!q.isEmpty()) {
            int i = q.poll();
            if (arr[i] == 0) return true;
            if (visited[i]) continue;
            visited[i] = true;
 
            int next1 = i + arr[i];
            int next2 = i - arr[i];
 
            if (next1 >= 0 && next1 < arr.length && !visited[next1]) q.offer(next1);
            if (next2 >= 0 && next2 < arr.length && !visited[next2]) q.offer(next2);
        }
        return false;
    }
}

The other languages (C++, Go, TypeScript) would follow a very similar structure, using their respective queue implementations and array/list handling. The core algorithm remains the same.