Jump Game III — BFS/DFS Reachability

Problem

From index start, you can jump to i + arr[i] or i - arr[i]. Return true if you can reach any index with value 0.

Solutions

Python — BFS

from collections import deque
class Solution:
    def canReach(self, arr: list[int], start: int) -> bool:
        n=len(arr); visited=set(); q=deque([start])
        while q:
            i=q.popleft()
            if arr[i]==0: return True
            if i in visited: continue
            visited.add(i)
            for j in [i+arr[i], i-arr[i]]:
                if 0<=j<n and j not in visited: q.append(j)
        return False

Python — DFS

class Solution:
    def canReach(self, arr: list[int], start: int) -> bool:
        n=len(arr); visited=set()
        def dfs(i):
            if not(0<=i<n) or i in visited: return False
            if arr[i]==0: return True
            visited.add(i)
            return dfs(i+arr[i]) or dfs(i-arr[i])
        return dfs(start)

Complexity

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