338. Jump Game III

Treat indices as graph nodes: from i there are edges to i+arr[i] and i-arr[i]. BFS (or DFS) from start, marking visited so we never loop, and succeed the moment we land on an index holding 0.

Indices are graph nodes

Each index i has at most two outgoing moves: to i + arr[i] and to i - arr[i] (when in bounds). Reaching a 0 is just a reachability question on this implicit graph, so do a breadth-first search from start.

The search

queue = [start]; visited = {}
while queue:
    i = queue.pop_front()
    if arr[i] == 0: return True
    if i already visited: continue
    mark i visited
    for j in (i + arr[i], i - arr[i]):
        if 0 <= j < n and j not visited: queue.push(j)
return False

The visited set guarantees each index is processed once, so the search is linear and can't loop forever.

Worked example

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

• 5 → arr[5]=1 → neighbors 6 and 4.
• 6 → arr[6]=2 → neighbor 4 (and 8 out of bounds).
• 4 → arr[4]=3 → neighbors 7 (out), 1.
• 1 → arr[1]=2 → neighbors 3, -1 (out).
• 3 → arr[3]=0 → return true.

Complexity

• Time: O(n) — each index enqueued at most once.
• Space: O(n) for the queue and visited set.

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] seen = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int i = queue.poll();
            if (arr[i] == 0) return true;
            if (seen[i]) continue;
            seen[i] = true;
            for (int j : new int[]{i + arr[i], i - arr[i]}) {
                if (j >= 0 && j < n && !seen[j]) queue.offer(j);
            }
        }
        return false;
    }
}