1306. Jump Game III

Problem¶

Given non-negative arr and starting index start, determine whether repeated jumps from index i to i - arr[i] or i + arr[i], without leaving the array, can reach any index containing 0.

arr = [4,2,3,0,3,1,2], start = 5
path: 5 -> 4 -> 1 -> 3
arr[3] = 0
output: True

Key trick¶

Treat indices as vertices in an implicit directed graph and run DFS or BFS, marking each index when discovered so cycles cannot revisit it.

Trap¶

Forgetting the visited check can cause infinite traversal or excessive memory use.
Marking an index only after removing it from the worklist allows duplicate insertions.
Jumps outside the array must be ignored.
Mutating arr to mark visits can unexpectedly alter the caller's input.

Why is it interesting?¶

It disguises a graph reachability problem as an array problem and tests cycle handling without explicitly constructing a graph.

Python solution¶

class Solution:
    def canReach(self, arr: list[int], start: int) -> bool:
        n = len(arr)
        stack = [start]
        visited = [False] * n
        visited[start] = True

        while stack:
            i = stack.pop()

            if arr[i] == 0:
                return True

            jump = arr[i]
            for nxt in (i - jump, i + jump):
                # Mark on discovery to prevent duplicate insertions.
                if 0 <= nxt < n and not visited[nxt]:
                    visited[nxt] = True
                    stack.append(nxt)

        return False

Time complexity: \(O(n)\).

Space complexity: \(O(n)\).

Comment on my solution¶

The approach is correct, but these statements compare instead of assigning:

arr[left_idx] == -1
arr[right_idx] == -1

They must be assignments:

arr[left_idx] = -1
arr[right_idx] = -1

Because neighbors are never marked, cyclic paths are repeatedly enqueued and eventually exhaust memory. Mark each neighbor before enqueueing it. Your approach also mutates arr; that is valid if explicitly allowed, but a separate visited structure avoids this side effect.

# Ideas:
# - treat arr as an directed graph each element being a vertex
# - start BFS at `start` and expand left and right until
#   reaching 0
# - mark in-place visited none with by setting array slot to -1

from collections import deque

# WRONG
# Memory Limit Exceeded: 3/56 testcases passed
# [1,1,1,1,2,0], 0
class Solution:
    def canReach(self, arr: list[int], start: int) -> bool:
        n = len(arr)
        if arr[start] == 0:
            return True

        q = deque([(start, arr[start])]) # index, jump
        arr[start] = -1

        while q:
            idx, jump = q.popleft()
            left_idx = idx - jump
            right_idx = idx + jump
            if 0 <= left_idx < n:
                next_jump = arr[left_idx]
                if next_jump == 0:
                    return True
                if next_jump != -1:
                    arr[left_idx] == -1
                    q.append((left_idx, next_jump))
            if 0 <= right_idx < n:
                next_jump = arr[right_idx]
                if next_jump == 0:
                    return True
                if next_jump != -1:
                    arr[right_idx] == -1
                    q.append((right_idx, next_jump))
        return False