Jump Game III: BFS Reachability Check

Given an array of non-negative integers arr and a starting index start, you can jump from index i to i + arr[i] or i - arr[i]. Your goal is to determine whether you can reach any index where arr[index] == 0.

This is LeetCode 1306: Jump Game III. Unlike the earlier Jump Game problems that ask about reaching the end of the array, this one asks whether you can reach a specific value anywhere in the array. The direction of exploration is different too: you jump both left and right by arr[i], not just forward.

Why this problem matters

Jump Game III is a bridge between array problems and graph problems. The array looks like a simple list of numbers, but the jump rules define edges between indices. Once you see that each index is a node and each valid jump is an edge, the problem becomes a standard graph reachability question: "can you reach a node with a particular property?"

This graph-on-an-array pattern shows up in many problems. "Open the Lock" (LeetCode 752), "Snakes and Ladders" (LeetCode 909), and "Minimum Jumps to Reach Home" (LeetCode 1654) all ask you to treat states as graph nodes and transitions as edges, then run BFS or DFS. Jump Game III is one of the cleanest examples of this pattern because the graph structure is so direct: index i has at most two outgoing edges.

The key insight

Every index in the array is a node. From node i, you have at most two edges: one to i + arr[i] and one to i - arr[i] (provided they stay in bounds). You need to find out whether any node reachable from start has value 0.

This is exactly what BFS (or DFS) does: explore all reachable nodes from a starting point. You enqueue start, then for each index you dequeue, you check if its value is 0. If yes, return True. If not, enqueue its valid, unvisited neighbors. If the queue empties without finding a 0, return False.

The visited set is critical. Without it, you could loop forever between two indices that jump to each other.

The solution

from collections import deque

def can_reach(arr, start):
    n = len(arr)
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        idx = queue.popleft()
        if arr[idx] == 0:
            return True
        for next_idx in [idx + arr[idx], idx - arr[idx]]:
            if 0 <= next_idx < n and next_idx not in visited:
                visited.add(next_idx)
                queue.append(next_idx)

    return False

The function starts by adding start to both the queue and the visited set. On each iteration, it pops an index from the front of the queue. If arr[idx] is 0, we found our target and return True immediately.

Otherwise, we compute the two possible jumps: idx + arr[idx] (right) and idx - arr[idx] (left). For each, we check two conditions: the new index must be within bounds (0 to n-1), and it must not have been visited already. If both conditions hold, we mark it visited and add it to the queue.

If the while loop finishes without returning True, every reachable index has been explored and none had value 0. We return False.

Visual walkthrough

Let's trace BFS on the example arr = [4, 2, 3, 0, 3, 1, 2] with start = 5. Watch how the queue evolves and how we discover the target at index 3.

The BFS found the 0-value index after visiting just five nodes. In the worst case it would visit every index in the array, but for many inputs the search terminates early as soon as a zero is found.

Complexity analysis

Time is O(n) where n is the length of the array. Each index enters the queue at most once (thanks to the visited set), and processing each index takes O(1) work: one check, two potential jumps, and constant-time set lookups.

Space is O(n) for the visited set and the BFS queue. In the worst case, every index is reachable and the visited set holds all n indices.

The building blocks

1. Graph modeling on arrays

The core technique is recognizing that an array with jump rules defines a graph. Each index is a node; each valid jump is a directed edge. This reframing turns an array problem into a graph traversal problem. You will see this same modeling step in "Jump Game," "Jump Game II," "Open the Lock," and any problem where transitions between states can be described as edges.

for next_idx in [idx + arr[idx], idx - arr[idx]]:
    if 0 <= next_idx < n:
        # next_idx is a neighbor of idx

2. BFS with a visited set

Standard BFS with cycle prevention. You enqueue the start, mark it visited, then repeatedly dequeue a node, process it, and enqueue unvisited neighbors. The visited set ensures you never process the same node twice, which prevents infinite loops in graphs with cycles.

visited = set()
queue = deque([start])
visited.add(start)

while queue:
    node = queue.popleft()
    for neighbor in get_neighbors(node):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

Edge cases

• Start index has value 0: arr[start] == 0, so BFS returns True on the very first iteration before exploring any neighbors.
• Single element array: arr = [0], start = 0. The only index has value 0. Return True. If arr = [5], there are no valid jumps and arr[0] != 0, so return False.
• No reachable zero: all reachable indices have nonzero values. BFS exhausts the queue and returns False.
• Disconnected regions: some indices might not be reachable from start. If the only zero-value index is in an unreachable region, the answer is False.
• Bidirectional jumps create cycles: for example, arr = [1, 1] with start = 0. Index 0 jumps to 1 and index 1 jumps to 0. Without the visited set, this would loop forever. With it, BFS visits both once and returns False.
• Jump lands exactly on boundary: idx + arr[idx] == n - 1 or idx - arr[idx] == 0. Both are valid. Make sure your bounds check uses 0 <= next_idx < n to include both endpoints.

From understanding to recall

You have seen how to model an array as a graph and run BFS to check reachability. The code is short and the logic is clear. But under interview conditions, the small decisions add up. Do you mark visited before or after enqueueing? Do you check arr[idx] == 0 before or after computing neighbors? Do you use 0 <= next_idx < n or 0 < next_idx < n?

These are not hard questions when you have time to think. But in a 45-minute interview, hesitating on these details eats minutes. Spaced repetition turns them into muscle memory. You practice writing the BFS loop, the visited check, and the graph modeling step from scratch at increasing intervals until you can produce them without pausing.

Related posts

• Jump Game - The original greedy reachability problem on arrays, where you track the farthest index you can reach
• Jump Game II - Extends the greedy approach to find the minimum number of jumps to reach the end
• Number of Islands - BFS/DFS on a grid to count connected components, another foundational graph traversal problem

CodeBricks breaks Jump Game III into its graph-modeling and BFS-traversal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a graph-on-array problem shows up in your interview, you do not think about it. You just write it.