---

1. Problem Summary

You are given an integer array arr and a starting index start.

From index i, you may move to:

i + arr[i]
or
i - arr[i]

Your task is to determine whether it is possible to reach any index with value 0.

Rules and constraints:

• You cannot move outside array bounds
• You may not revisit the same index repeatedly (infinite loop risk)
• If any reachable index holds value 0, return true
• Otherwise return false

Example:

Input:  arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
5 → 4 → 0 (found zero)

---

2. Key Insights

Insight 1: This is a reachability problem

We are exploring reachable positions from a starting index.

Insight 2: Graph interpretation

• Each index is a node
• Edges point to:
  • i + arr[i]
  • i – arr[i]

Insight 3: Must avoid revisiting visited indices

Without visited tracking, recursion or BFS would loop infinitely (e.g., arr contains zeros or cycles).

Insight 4: BFS or DFS both work

Either traversal eventually explores all reachable indices.

Insight 5: Stop early upon finding arr[i] == 0

No need to keep exploring once a zero index is reached.

---

3. Approach

BFS Approach (recommended for clarity)

Steps:

1. Create a queue and enqueue start
2. Maintain a visited boolean array
3. While queue not empty:
   • dequeue index i
   • if arr[i] == 0 → return true
   • compute next1 = i + arr[i]
   • compute next2 = i – arr[i]
   • if next positions are within bounds and not visited → enqueue them
4. If queue empties without success → return false

---

4. Time and Space Complexity

Time Complexity:

O(N)

Each index processed at most once.

Space Complexity:

O(N)

Visited array + BFS queue.

---

5. Java Solution (BFS)

import java.util.*;

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int index = queue.poll();

            if (arr[index] == 0) {
                return true;
            }

            int forward = index + arr[index];
            int backward = index - arr[index];

            if (forward >= 0 && forward < n && !visited[forward]) {
                visited[forward] = true;
                queue.offer(forward);
            }

            if (backward >= 0 && backward < n && !visited[backward]) {
                visited[backward] = true;
                queue.offer(backward);
            }
        }

        return false;
    }
}

---

6. DFS Alternative (recursive)

class Solution {
    public boolean canReach(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        return dfs(arr, start, visited);
    }

    private boolean dfs(int[] arr, int index, boolean[] visited) {
        if (index < 0 || index >= arr.length || visited[index]) {
            return false;
        }

        if (arr[index] == 0) {
            return true;
        }

        visited[index] = true;

        return dfs(arr, index + arr[index], visited)
            || dfs(arr, index - arr[index], visited);
    }
}

---

7. Dry Run Examples

Example 1

Input:

arr = [4,2,3,0,3,1,2], start = 5

Traversal:

start = 5 → value=1
next = 6 or 4
6 → value=2 → next = 4 or 2
4 → value=3 → next = 1 or 7(out)
1 → value=2 → next = 3 or -1
3 → value=0 → success

Output:

true

---

Example 2

Input:

arr = [3,0,2,1,2], start = 2

Traversal:

2 → value=2 → next = 4 or 0
4 → value=2 → next = 6(out) or 2 (visited)
0 → value=3 → next = 3 or -3(out)
3 → value=1 → next = 4 (visited) or 2 (visited)
No zero reached

Output:

false

---

Example 3

Input:

arr = [0], start = 0

Start index already zero

Output:

true

---

Example 4

Input:

arr = [1,1,1,1,0,1], start = 3

3 → 4 → found zero

Output:

true

---

Example 5

Input:

arr = [2,4,1,3,0,2], start = 1

reachable chain eventually hits zero

Output:

true

---

8. Why This Solution Works

• Bounds checks prevent invalid transitions
• Visited tracking prevents loops
• BFS/DFS ensures reachable space explored fully
• Stops immediately on success
• Works even with:
  • cycles
  • repeated numbers
  • start far from zero

---

9. Common Mistakes

1. Forgetting visited array → infinite recursion or looping
2. Not checking bounds correctly
3. Thinking array must be sorted (it need not be)
4. Assuming movement only forward
5. Returning false too early before exploring all paths