Jump Game III

medium array breadth-first search graph

Problem

Given an array of non-negative integers arr and a starting index start, from index i you may jump to i + arr[i] or i - arr[i] (never outside the array). Return true if you can reach any index whose value is 0.

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

Outputtrue

5 → 4 → 1 → 3, and arr[3] = 0, so a zero is reachable.

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

Outputfalse

No sequence of jumps from index 2 ever lands on the zero at index 1.

arr (comma-separated, non-negative)

start index

def can_reach(arr, start):
    n = len(arr)
    queue = [start]
    seen = [False] * n
    seen[start] = True
    while queue:
        i = queue.pop(0)
        if arr[i] == 0:
            return True
        for nxt in (i + arr[i], i - arr[i]):
            if 0 <= nxt < n and not seen[nxt]:
                seen[nxt] = True
                queue.append(nxt)
    return False

function canReach(arr, start) {
  const n = arr.length;
  const queue = [start];
  const seen = new Array(n).fill(false);
  seen[start] = true;
  while (queue.length) {
    const i = queue.shift();
    if (arr[i] === 0) return true;
    for (const nxt of [i + arr[i], i - arr[i]]) {
      if (nxt >= 0 && nxt < n && !seen[nxt]) {
        seen[nxt] = true;
        queue.push(nxt);
      }
    }
  }
  return false;
}

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

bool canReach(vector<int>& arr, int start) {
    int n = arr.size();
    queue<int> q;
    q.push(start);
    vector<bool> seen(n, false);
    seen[start] = true;
    while (!q.empty()) {
        int i = q.front(); q.pop();
        if (arr[i] == 0) return true;
        for (int nxt : {i + arr[i], i - arr[i]}) {
            if (nxt >= 0 && nxt < n && !seen[nxt]) {
                seen[nxt] = true;
                q.push(nxt);
            }
        }
    }
    return false;
}

Explanation

Think of the array as a graph: each index i has at most two outgoing edges, to i + arr[i] and i - arr[i]. The question "can I reach a zero?" becomes "is any zero-valued index reachable from start?", a classic reachability problem.

We solve it with breadth-first search. A queue holds indices waiting to be explored, and a seen array stops us from revisiting an index (which would otherwise loop forever).

Each iteration pops an index i from the front of the queue. If arr[i] == 0 we have found a zero and immediately return true. Otherwise we compute the two jump targets, keep only those that stay in bounds and are unseen, mark them, and enqueue them.

If the queue drains without ever landing on a zero, no zero is reachable and we return false.

Each index is enqueued at most once, so the search visits every reachable node a single time. With n indices this runs in O(n) time and O(n) space. A DFS (recursion or explicit stack) works equally well; BFS just explores level by level.

Time: O(n) Space: O(n)