Problem Statement in English

You’re given an array of non-negative integers arr, where each element represents the maximum jump length at that position. You’re also given a starting index start. Your task is to determine if you can reach any index with a value of 0 by jumping according to the rules defined by the array.

Return true if you can reach an index with a value of 0, and false otherwise.

Approach

To solve this problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the possible jumps from the starting index. We will maintain a stack (for DFS) or a queue (for BFS) to keep track of the indices we can jump to, and a set to keep track of the indices we’ve already visited to avoid cycles.

And we’re done!

Solution in Python


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)

        stack = [start]
        seen = set()

        while stack:
            node = stack.pop()

            if node in seen:
                continue
            seen.add(node)
            
            if arr[node] == 0:
                return True
            
            for x in [node + arr[node], node - arr[node]]:
                if x not in seen and 0 <= x < n:
                    stack.append(x)

        return False

Complexity

  • Time: $O(n)$
    Since we visit each node at most once.

  • Space: $O(n)$
    Since we store the seen nodes in a set.

And we are done.