1306. Jump Game III

Array
BFS
DFS

TIME

O(n)

SPACE

O(n)

Intuition

Treat each index as a node in a graph. From index i, there are at most two outgoing edges:

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

The question is whether any reachable node has value 0.

Because cycles are possible, we need a visited array.

Approach

Start BFS from start.
Mark start as visited.
While the queue is not empty:
- pop an index
- if arr[index] == 0, return true
- try both next indices
- enqueue valid, unvisited indices
If BFS finishes without finding 0, return false.

Complexity

Time: O(n), each index is visited at most once
Space: O(n), for the queue and visited array

Edge Cases

arr[start] == 0 -> return true
Jump value is 0 at a non-start index
Cycles between indices -> handled by visited
Jumps outside bounds -> ignored

Code

from collections import deque
from typing import List


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        """
        1306. Jump Game III
        Time: O(n)
        Space: O(n)
        """
        n = len(arr)
        visited = [False] * n
        queue = deque([start])
        visited[start] = True

        while queue:
            index = queue.popleft()

            if arr[index] == 0:
                return True

            for next_index in (index + arr[index], index - arr[index]):
                if 0 <= next_index < n and not visited[next_index]:
                    visited[next_index] = True
                    queue.append(next_index)

        return False

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 1306. Jump Game III
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();

        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 < n && !visited[forward]) {
                visited[forward] = true;
                queue.offer(forward);
            }

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

        return false;
    }
}