Jump Game III — BFS / DFS Reachability on an Implicit Graph

Problem Statement#

LeetCode 1306 — Jump Game III (Medium)

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach any index with value 0.

Notice that you cannot jump outside of the array at any time.

Constraints:

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

Example 1:

arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: Path 5 -> 4 (5-1) -> 1 (4-3) -> 3 (1+2). arr[3] == 0.

Example 2:

arr = [4,2,3,0,3,1,2], start = 0
Output: true (jump 0 -> 4 -> 1 -> 3, arr[3] == 0)

Example 3:

arr = [3,0,2,1,2], start = 2
Output: false (no sequence of jumps reaches the index whose value is 0)

Why This Problem Matters#

Jump Game III is the textbook example of an implicit graph — a problem that does not explicitly hand you nodes and edges, but where the solution becomes obvious once you build them in your head. Amazon and Google both use it as a screening question because it tests whether candidates can:

1. Recognize the graph structure in a problem that looks like array manipulation. Each index i has at most two outgoing edges: to i + arr[i] and i - arr[i].
2. Apply standard BFS or DFS without getting confused by the array indexing.
3. Use a visited set correctly so that revisiting an index is impossible — without that, the algorithm loops forever (try start = 5 in [1,1,1,1]).

Once you see the graph, the problem collapses from looking impossible to being a five-minute solve. That moment of recognition is exactly what interviewers reward.

The Core Insight#

Build the implicit graph mentally:

• Nodes: array indices 0 through n - 1.
• Edges: from i, two directed edges to i + arr[i] and i - arr[i] if those indices stay inside the array.
• Goal: any node j such that arr[j] == 0 is a valid destination.

The question becomes "can I reach any zero-valued node from start?" That is a textbook reachability problem solvable by either BFS or DFS in O(N) time, since each index is visited at most once and produces at most two neighbors.

A subtle observation: once arr[i] is zero, the only outgoing edges go to i + 0 = i and i - 0 = i, both of which are itself. So zero-valued indices act as terminal sinks — exactly what we want.

Visual Dry Run#

arr = [4,2,3,0,3,1,2], start = 5. Build the BFS frontier:

queue = [5], visited = {5}
 
Pop 5. arr[5] = 1.
  neighbors: 5+1 = 6, 5-1 = 4
  arr[6] = 2 (not zero), arr[4] = 3 (not zero)
  push 6, 4. visited = {5, 6, 4}
 
Pop 6. arr[6] = 2.
  neighbors: 6+2 = 8 (out of bounds), 6-2 = 4 (visited)
  nothing new
 
Pop 4. arr[4] = 3.
  neighbors: 4+3 = 7 (out of bounds), 4-3 = 1
  push 1. visited = {5, 6, 4, 1}
 
Pop 1. arr[1] = 2.
  neighbors: 1+2 = 3, 1-2 = -1 (out of bounds)
  arr[3] == 0 -> return true.

Notice that we check the value before pushing, not after. This avoids one extra dequeue step.

Solution (Optimal)#

Python (BFS)#

from collections import deque
 
class Solution:
    def canReach(self, arr: list[int], start: int) -> bool:
        n = len(arr)
 
        # Edge case: starting on a zero immediately wins
        if arr[start] == 0:
            return True
 
        visited = {start}
        queue = deque([start])
 
        while queue:
            i = i = queue.popleft()           # current index
            step = arr[i]                       # jump distance from this cell
 
            for nxt in (i + step, i - step):    # two possible neighbors
                if 0 <= nxt < n and nxt not in visited:
                    if arr[nxt] == 0:
                        return True             # reached a zero-valued index
                    visited.add(nxt)            # mark on enqueue, not on dequeue
                    queue.append(nxt)
 
        return False                             # exhausted component without zero

JavaScript (DFS — in-place visited marking)#

/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 *
 * Negate visited values so we don't need an external set.
 * Constraint: 0 <= arr[i] < arr.length, so all values are non-negative.
 * After visit we negate; arr[i] < 0 means visited.
 */
var canReach = function(arr, start) {
    const n = arr.length;
 
    const dfs = (i) => {
        if (i < 0 || i >= n || arr[i] < 0) return false;  // out of bounds or visited
        if (arr[i] === 0) return true;                     // found a zero-valued index
        const step = arr[i];
        arr[i] = -arr[i];                                  // mark visited in place
        // Try both jump directions; short-circuit on success
        return dfs(i + step) || dfs(i - step);
    };
 
    return dfs(start);
};

Complexity. Each index is visited at most once and produces a constant amount of work per visit, so time and space are both O(N). The DFS solution mutates the input — restore it if your caller needs the original array.

Common Mistakes#

1. Skipping the visited set. Without it the algorithm loops forever on inputs like [1,1,1,1] starting at index 0. The first jump goes to 1, the next jump comes back to 0, and so on.
2. Confusing arr[i] == 0 with i == 0. The destination is any value equal to zero, not the index zero. Read carefully.
3. Bounds checks placed after the value check. Always validate 0 <= nxt and nxt smaller than n before accessing arr[nxt], or you will read out of bounds.
4. Recursive DFS with deep arrays. With n up to 50,000 a chain graph can blow the recursion stack in Python. Use iterative BFS for that case or bump the recursion limit.
5. Forgetting the trivial case arr[start] == 0. Some implementations check the value only when popping a neighbor and miss the start itself.

Interview Tips#

• State the implicit graph translation explicitly. "Each index is a node with up to two outgoing edges based on its value." This single sentence reframes the problem from puzzle to standard traversal.
• Choose your algorithm out loud. BFS is safer because it cannot blow the recursion stack. DFS is shorter but riskier; mention the trade-off.
• Mention the in-place visited trick as an optimization if memory matters. Negating values works because the constraint guarantees non-negativity.
• Walk Example 2 because it requires multiple jumps and exercises the visited set.

Follow-up Questions#

1. Return the shortest jump path to a zero. Use BFS and track the depth of each node. Return depth on first zero.
2. Allow more than two jump options. The graph degree increases but the algorithm does not change — adjust the neighbors loop.
3. Negative values allowed. Some variants allow arr[i] smaller than 0. The algorithm still works; just verify bounds.
4. Dynamic updates. If arr mutates between queries, you cannot cache. Each query becomes O(N).
5. Multiple start points. Multi-source BFS: enqueue every starting index at depth 0.

Key Takeaways#

• Jump Game III is an implicit graph problem — the array hides nodes and edges that you must construct mentally.
• Either BFS or DFS solves it in O(N) time and O(N) space because each index has at most two outgoing edges.
• A visited set is mandatory; without it the algorithm cycles forever.
• The in-place visited trick (negating values) saves memory but requires the input to be mutable.
• Always check the destination predicate before enqueue, not after dequeue, for cleaner code.
• Recognizing implicit graphs is one of the most reusable interview skills — it appears in LC 752 (Open the Lock), LC 815 (Bus Routes), and LC 1129.