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 to any index with value 0.
Notice that you can not jump outside of the array at any time.
 
Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 

Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

 
Constraints:

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

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        dq = collections.deque([start])
        visited = set([start])
        
        while dq:
            
            curr = dq.pop()
            
            if arr[curr] == 0:
                return True
            
            if (curr + arr[curr]) not in visited and (curr + arr[curr]) < len(arr):
                dq.appendleft(curr + arr[curr])
                visited.add(curr + arr[curr])
            if (curr - arr[curr]) not in visited and (curr - arr[curr]) >= 0:
                dq.appendleft(curr - arr[curr])
                visited.add(curr - arr[curr])
        
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        if 0 not in arr:
            return False
        visited = set()
        queue = []
        queue.append(start)
        visited.add(start)
        while len(queue):
            curr_index = queue.pop()
            if arr[curr_index] == 0:
                return True
            next_index = curr_index + arr[curr_index]
            if next_index < len(arr) and next_index not in visited:
                visited.add(next_index)
                queue.append(next_index)
            next_index = curr_index - arr[curr_index]
            if next_index >= 0 and next_index not in visited:
                visited.add(next_index)
                queue.append(next_index)
        return False
                
            
        
        


import sys
sys.setrecursionlimit(10**6) 

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:  
        return self.canReach2(arr, start, [])
        
    def canReach2(self, arr, start, visited):
        if start >= len(arr) or start < 0 or start in visited:
            return False
        if arr[start] == 0:
            return True

        visited.append(start)
        # print(start)
        res = self.canReach2(arr, start + arr[start], visited) or self.canReach2(arr, start - arr[start], visited)
        if res is False:
            visited.pop()
        return res

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        def jump(arr, start, n, g):
            g+=1
            if g>25:
                return False
            if start<0 or start>n-1:
                return False
            
            if arr[start] == 0:
                return True
            
            if jump(arr, start+arr[start],n,g):
                return True
            else:
                if jump(arr,start-arr[start],n,g):
                    return True
                else:
                    return False
            
        return jump(arr,start,len(arr),0)

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        memo = {}
        def dfs(i):
            if arr[i] == 0:
                return True
            if i in memo:
                return memo[i]
            memo[i] = False
            new_i = i + arr[i]
            if 0 <= new_i < len(arr):
                if dfs(new_i):
                    memo[i] = True
                    return True
            new_i = i - arr[i]
            if 0 <= new_i < len(arr):
                if dfs(new_i):
                    memo[i] = True
                    return True
            
            return memo[i]
        
        return dfs(start)

class Solution:
    def canReach(self, jumps: List[int], start: int) -> bool:
        st = [start]
        size = len(jumps)
        
        while st:
            idx = st.pop()
            jump = jumps[idx]
            # print(jump, st)
            if jump < 0:
                continue
            
            left, right = idx - jump, idx + jump
            for i in [left, right]:
                if 0 <= i < size:
                    if jumps[i] == 0:
                        return True
                    st.append(i)
            jumps[idx] = -1
        
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        if 0 <= start < len(arr) and arr[start] >= 0:
            if arr[start] == 0:
                return True

            arr[start] = -arr[start]
            return self.canReach(arr, start+arr[start]) or self.canReach(arr, start-arr[start])

        return False



class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        visited_indices = set()
        
        def visit(index: int):
            if index < 0 or index >= len(arr):
                return False
            
            if index in visited_indices:
                return False
            if arr[index] == 0:
                return True
            visited_indices.add(index)
                
            a = visit(index + arr[index])
            b = visit(index - arr[index])
            return a or b
            
        
        return visit(start)

# 20201002 Jenny sample 200 ms submission
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        v=set()
        q = [start]
        while q:
            i = q.pop()
            v.add(i)
            if arr[i]==0:
                return True
            for idx in [(i+arr[i]),i-arr[i]]:
                if 0<=idx<len(arr) and idx not in v:
                    q.append(idx)
        return False

from collections import defaultdict, deque

class Solution:
    
    def canReach(self, arr: List[int], start: int) -> bool:
        zero_value = set([])
        
        for i in range(len(arr)):
            if arr[i] == 0:
                zero_value.add(i)
        
        # bfs
        queue = deque([start])
        seen = set([])
        while queue:
            i = queue.popleft()
            if i in zero_value:
                return True
            seen.add(i)

            up = i + arr[i]
            if up < len(arr) and up not in seen:
                queue.append(up)
            down = i - arr[i]
            if down >=0 and down not in seen:
                queue.append(down)
        
        return False

#     def canReach(self, arr: List[int], start: int) -> bool:
#         graph = defaultdict(set)
#         zero_value = set([])
        
#         for i in range(len(arr)):
#             if arr[i] == 0:
#                 zero_value.add(i)
#             else:
#                 if i + arr[i] < len(arr):
#                     graph[i].add(i + arr[i])
#                 if i - arr[i] >=0:
#                     graph[i].add(i - arr[i]) 
        
#         # bfs
#         queue = deque([start])
#         seen = set([])
#         while queue:
#             item = queue.popleft()
#             if item in zero_value:
#                 return True
#             seen.add(item)

#             for nei in graph[item]:
#                 if nei not in seen:
#                     queue.append(nei)
        
#         return False


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        visited = []
        if arr[start] == 0:
            return True
        currNodes = [start]
        
        while len(visited) < len(arr):
            temp = []
            for i in currNodes:
                visited += [i]
                candidate1 = i+arr[i]
                candidate2 = i-arr[i]
                if candidate1 < len(arr) and candidate1 not in visited:
                    if arr[candidate1] == 0:
                        return True
                    temp += [candidate1]
                if candidate2 >= 0 and candidate2 not in visited:
                    if arr[candidate2] == 0:
                        return True
                    temp += [candidate2]
            if len(temp) == 0:
                break
            currNodes = temp
        return False
                    


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        q = deque([start])
        visited = set()
        while q:
            curr = q.popleft()
            if arr[curr]==0: return True
            if curr not in visited:
                visited.add(curr)
                if curr+arr[curr]<len(arr):
                    q.append(curr+arr[curr])
                if curr-arr[curr]>=0:
                    q.append(curr-arr[curr])
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        size = len(arr)
        visited = [[0]*2 for _ in range(size)]
        def trackback(index):
            if arr[index] == 0:
                return True
            if index + arr[index] < size and visited[index][1] == 0:
                visited[index][1] = 1
                if trackback(index+arr[index]):
                    return True
            if index - arr[index] > -1 and visited[index][0] == 0:
                visited[index][0] = 1
                if trackback(index - arr[index]):
                    return True
            return False
        return trackback(start)

from collections import deque

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
            
        queue = deque([start])
        seen = set()
        
        while queue:
            curr_index = queue.popleft()
            seen.add(curr_index)
            if arr[curr_index] == 0:
                return True
            if curr_index - arr[curr_index] >= 0 and curr_index - arr[curr_index] not in seen:
                queue.append(curr_index - arr[curr_index])
            if curr_index + arr[curr_index] < len(arr) and curr_index + arr[curr_index] not in seen:
                queue.append(curr_index + arr[curr_index])
                    
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        if not arr: return False
        if start<0 or start>=len(arr): return False
        
        queue = collections.deque()
        queue.append(start)
        visited = set([start])
        while queue:
            curr = queue.popleft()
            if arr[curr] == 0:
                return True
            if 0<=curr+arr[curr]<len(arr) and curr+arr[curr] not in visited:
                queue.append(curr+arr[curr])
                visited.add(curr+arr[curr])
            if 0<=curr-arr[curr]<len(arr) and curr-arr[curr] not in visited:
                queue.append(curr-arr[curr])
                visited.add(curr-arr[curr])
                
        return False


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        size = len(arr)
        visited = [0] * size
        def trackback(index):
            if arr[index] == 0:
                return True
            if index + arr[index] < size and visited[index+arr[index]] == 0:
                visited[index+arr[index]] = 1
                if trackback(index+arr[index]):
                    return True
            if index - arr[index] > -1 and visited[index-arr[index]] == 0:
                visited[index - arr[index]] = 1
                if trackback(index - arr[index]):
                    return True
            return False
        visited[start] = 1
        return trackback(start)

from collections import deque
from functools import reduce
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        if not arr:
            return False
        if arr[start] == 0:
            return True

        def add_edge(nodes, edge):
            index, jump = edge
            if jump == 0:
                nodes[index].append(index)
                return nodes
            if (back:=index-jump) >= 0:
                nodes[index].append(back)
            if (forw:=index+jump) < len(arr):
                nodes[index].append(forw)
            return nodes    
            
        edges = reduce(add_edge, enumerate(arr), defaultdict(list))
        
        q = deque([start])
        visited = {start}
        while q:
            popped = q.popleft()
            for n in edges[popped]:
                if n == popped:
                    return True
                if n in visited:
                    continue
                visited.add(n) 
                q.append(n)
        return False     
        
        


class Solution:
    # returns an adjacency list representation of graph
    def genGraph(self, arr: List[int]) -> List[List[int]]:
        adjList = [[] for i in range(len(arr))]
        for i in range(len(arr)):
            left = i - arr[i]
            right = i + arr[i]
            if left >= 0:
                adjList[i].append(left)
            if right < len(arr):
                adjList[i].append(right)
        return adjList
    
    def canReach(self, arr: List[int], start: int) -> bool:
        graph = self.genGraph(arr)
        bfsQueue = [start]
        visited = set()
        while len(bfsQueue) > 0:
            node = bfsQueue.pop(0)
            if arr[node] == 0:
                return True
            if node in visited:
                break
            visited.add(node)
            for neighbour in graph[node]:
                if neighbour not in visited:
                    bfsQueue.append(neighbour)
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        graph = defaultdict(list)
        for i in range(len(arr)):
            if i+arr[i]< len(arr):
                graph[i].append(i+arr[i])
            if i-arr[i]>=0:
                graph[i].append(i-arr[i])
        def isReachable( s, d,graph): 
            # Mark all the vertices as not visited 
            visited =[False]*(len(arr)) 

            # Create a queue for BFS 
            queue=[] 

            # Mark the source node as visited and enqueue it 
            queue.append(s) 
            visited[s] = True

            while queue: 

                #Dequeue a vertex from queue  
                n = queue.pop(0) 

                # If this adjacent node is the destination node, 
                # then return true 
                if arr[n] == d: 
                    return True

                #  Else, continue to do BFS 
                for i in graph[n]: 
                    if visited[i] == False: 
                        queue.append(i) 
                        visited[i] = True
             # If BFS is complete without visited d 
            return False
        return isReachable(start,0,graph)

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        graph = {}
        
        for i in range(len(arr)):
            graph[i] = []
            if arr[i] == 0: continue
            if i + arr[i] < len(arr): graph[i] += [i+arr[i]]
            if i - arr[i] >= 0: graph[i] += [i-arr[i]]
                
        stack = [start]
        seen = set([start])
        
        while len(stack) > 0: 
            curr = stack.pop()
            seen.add(curr)
            if len(graph[curr]) == 0 and arr[curr] == 0: return True
            for adj in graph[curr]: 
                if adj not in seen: stack.append(adj)
            
            
        return False

class Solution:
    def recursion(self,arr,index,s):
        if (index<0) | (index>=len(arr)):
            return False
        elif arr[index] == 0:
            return True
        elif index in s:
            return False
        else:
            s.add(index)
            return self.recursion(arr,index+arr[index],s) | self.recursion(arr,index-arr[index],s) 
    def canReach(self, arr: List[int], start: int) -> bool:
        if 0 not in arr:
            return False
        s = set()
        return self.recursion(arr,start,s)
        


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        graph = {}
        
        for i in range(len(arr)):
            graph[i] = []
            if arr[i] == 0: continue
            if i + arr[i] < len(arr): graph[i] += [i+arr[i]]
            if i - arr[i] >= 0: graph[i] += [i-arr[i]]
                
        stack = [start]
        seen = set([start])
        
        while len(stack) > 0: 
            curr = stack.pop()
            seen.add(curr)
            if arr[curr] == 0: return True
            for adj in graph[curr]: 
                if adj not in seen: stack.append(adj)
            
            
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        seen = set()
        
        def steps(i):
            for next in [i + arr[i], i - arr[i]]:
                if next >= 0 and next < len(arr) and next not in seen:
                    seen.add(next)
                    yield next
                    
        q = collections.deque()
        
        q.append(start)
        
        while q:
            c = q.popleft()
            for next in steps(c):
                if arr[next] == 0:
                    return True
                q.append(next)
        return False
                
        
        


class Solution:
    
    def dfs(self, graph, arr, root):
        stack = []
        stack.append(root)
        visited = set()
        while len(stack) > 0:
            current = stack.pop()
            if current in visited:
                continue
            visited.add(current)
            if arr[current] == 0:
                return True
            # check the neighbors
            for n in graph.get(current, []):
                stack.append(n)
        return False
    
    def canReach(self, arr: List[int], start: int) -> bool:
        graph = dict()
        for i in range(len(arr)):
            graph[i] = graph.get(i, [])
            if 0 <= i + arr[i] < len(arr):
                graph[i].append(i + arr[i])
            if 0 <= i - arr[i] < len(arr):
                graph[i].append(i - arr[i])
        return self.dfs(graph, arr, start)

if False:
    print((Solution().canReach([4,2,3,0,3,1,2], 0))) # true
    print((Solution().canReach([3,0,2,1,2], 2))) # false
    


class Solution:
    def canReach(self, jumps: List[int], start: int) -> bool:
        size = len(jumps)
        reach = [[] for i in range(size)]
        
        for pos, jump in enumerate(jumps):
            l, r = pos - jump, pos + jump
            if l >= 0 and pos not in reach[l]:
                reach[l].append(pos)
            if r < size and pos not in reach[r]:
                reach[r].append(pos)
            
        def do(idx, path=set()):
            if idx == start:
                return True
            for prev in reach[idx]:
                if prev not in path and do(prev, path | {prev}):
                    return True
            return False
        # print(reach)
        for p, n in enumerate(jumps):
            if n == 0 and do(p):
                return True
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        visited = [False] * n
        def dfs(index:int)->bool:
            if index < 0 or index >= n:
                return False
            if visited[index]:
                return False
            if arr[index] == 0:
                return True
            visited[index] = True
            left = index - arr[index]
            if dfs(left):
                return True
            right = index + arr[index]
            return dfs(right)
        return dfs(start)
        return ans


from collections import defaultdict, deque

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        graph = defaultdict(set)
        zero_value = set([])
        
        for i in range(len(arr)):
            if arr[i] == 0:
                zero_value.add(i)
            else:
                if i + arr[i] < len(arr):
                    graph[i].add(i + arr[i])
                if i - arr[i] >=0:
                    graph[i].add(i - arr[i]) 
        
        # bfs
        queue = deque([start])
        seen = set([])
        while queue:
            for i in range(len(queue)):
                item = queue.popleft()
                if item in zero_value:
                    return True
                seen.add(item)
                
                for nei in graph[item]:
                    if nei not in seen:
                        queue.append(nei)
        
        return False


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        if 0 <= start < len(arr) and arr[start] >= 0:
            if arr[start] == 0:
                return True

            arr[start] = -arr[start]
            return self.canReach(arr, start+arr[start]) or self.canReach(arr, start-arr[start])

        return False


from collections import defaultdict, deque

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        graph = defaultdict(set)
        zero_value = set([])
        
        for i in range(len(arr)):
            if arr[i] == 0:
                zero_value.add(i)
            else:
                if i + arr[i] < len(arr):
                    graph[i].add(i + arr[i])
                if i - arr[i] >=0:
                    graph[i].add(i - arr[i]) 
        
        # bfs
        queue = deque([start])
        seen = set([])
        while queue:
            item = queue.popleft()
            if item in zero_value:
                return True
            seen.add(item)

            for nei in graph[item]:
                if nei not in seen:
                    queue.append(nei)
        
        return False


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        graph = [set() for _ in range(n)]
        for i, j in enumerate(arr):
            if i+j < n:
                graph[i].add(i+j)
            if i-j >= 0:
                graph[i].add(i-j)
                
        self.graph = graph        
        self.visited = set()
        return self.dfs(start)
        
    def dfs(self, i):
        if i in self.visited:
            return False
        self.visited.add(i)
        if i in self.graph[i]:
            return True
        else:
            for j in self.graph[i]:
                if self.dfs(j):
                    return True

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        def solve(arr, i, done):
            if arr[i] == 0:
                return True
            elif i in done:
                return False
            else:
                a,b = False, False
                if 0 <= i + arr[i] < len(arr):
                    done[i] = 1
                    a = solve(arr, i + arr[i], done)
                if 0 <= i - arr[i] < len(arr):
                    done[i] = 1
                    b = solve(arr, i - arr[i], done)
                return a or b
        return solve(arr, start, {})

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        q = [start]
        
        while q:
            node = q.pop(0)
            if arr[node] == 0:
                return True
            if arr[node] < 0:
                continue
            for i in [node+arr[node], node-arr[node]]:
                if 0 <= i < n:
                    q.append(i)
            arr[node] = -1
        
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        seen = set()
        
        def canReachRec(ix):
            if ix < 0 or ix >= len(arr):
                return False
            if ix in seen:
                return False
            if arr[ix] == 0:
                return True

            seen.add(ix)
            if canReachRec(ix + arr[ix]):
                return True
            if canReachRec(ix - arr[ix]):
                return True
            return False
        return canReachRec(start)


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        adj={i:[] for i in range(len(arr))}
        target={}
        
        for idx,jump in enumerate(arr):
            choice_a=idx-jump
            choice_b=idx+jump
            if choice_a>=0 and choice_a<len(arr):
                adj[idx].append(choice_a)
            if choice_b>0 and choice_b<len(arr):
                adj[idx].append(choice_b)
            if jump==0:
                target[idx]=True
            else:
                target[idx]=False
        q=deque([start])
        visited=[]
        while q:
            cur=q[0]
            q.popleft()
            visited.append(cur)
            for neighbor in adj[cur]:
                if target[neighbor]:
                    return True
                if neighbor not in visited:
                    q.append(neighbor)
        return False


class Solution:
    def canReach1(self, arr: List[int], start: int) -> bool:
        # recursive helper function
        # recurse both left, right from i-th position
        # invert arr value to check only once
        # O(N) time, space in recursive stack

        def rcrs(i):
            if (0 <= i < len(arr)) and (arr[i] >= 0):
                if arr[i] == 0:
                    return True

                arr[i] = -arr[i]
                left_able = rcrs(i + arr[i])
                right_able = rcrs(i - arr[i])
                return left_able or right_able
            return False

        # recursive call
        return rcrs(start)

    def canReach(self, arr: List[int], start: int) -> bool:
        # try iteratively: add values to deque w/ value inversion
        # O(N) time, O(N) space

        q = collections.deque([start])

        while q:
            i = q.popleft()

            if (0 <= i < len(arr)) and arr[i] >= 0:
                if arr[i] == 0:
                    return True

                arr[i] = -arr[i]
                q.append(i+arr[i]) # left
                q.append(i-arr[i]) # right
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        visited = set()
        
        def helper(i):
            if i in visited:
                return False
            
            if arr[i] == 0:
                return True
            
            visited.add(i)
            
            left = helper(i-arr[i]) if i - arr[i] >= 0 else False
            right = helper(i + arr[i]) if i + arr[i] < len(arr) else False
            return left or right
        
        return helper(start)

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        seen=set()
        return self.dfs(arr,start,seen)
    
    def dfs(self,arr,idx,seen):
        if idx>=len(arr) or (idx<0) or (idx in seen):
            return False
        if arr[idx]==0:
            return True
        seen.add(idx)
        return self.dfs(arr,idx-arr[idx],seen) or self.dfs(arr,idx+arr[idx],seen)

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        nums = arr
        update = True
        while update:
            update = False
            for i in range(len(nums)):
                j = nums[i]
                if nums[i] == 0:
                    continue
                
                if i-j>=0 and nums[i-j]==0:
                    nums[i] = 0
                    update = True
                    
            for i in reversed(list(range(len(nums)))):
                j = nums[i]
                if nums[i] == 0:
                    continue
                
                if i+j<len(nums) and nums[i+j]==0:
                    nums[i] = 0
                    update = True
        
        return nums[start] == 0
                    


from functools import lru_cache

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        def dfs(idx, visited):
            if arr[idx] == 0:
                return True
            left_idx = idx-arr[idx]
            if left_idx >= 0 and left_idx not in visited:
                visited.add(left_idx)
                res = dfs(left_idx, visited)
                if res:
                    return True            
            right_idx = idx+arr[idx]
            if right_idx < len(arr) and right_idx not in visited:
                visited.add(right_idx)
                res = dfs(right_idx, visited)
                if res:
                    return True
            return False
        
        return dfs(start, set([start]))


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        q = collections.deque()
        visited = set()
        q.append(start)
        visited.add(start)
        while len(q) > 0:
            curr_idx = q.popleft()
            if arr[curr_idx] == 0:
                return True
            for next_idx in [curr_idx + arr[curr_idx], curr_idx - arr[curr_idx]]:
                if 0 <= next_idx < len(arr):
                    if next_idx not in visited:
                        q.append(next_idx)
                        visited.add(next_idx)
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        q = deque([start])
        visited = set()
        N = len(arr)
        while q:
            cur = q.popleft()
            if cur in visited: continue
            visited.add(cur)
            if arr[cur] == 0: return True
            if cur + arr[cur] < N:
                q.append(cur + arr[cur])
            if cur - arr[cur] >= 0:
                q.append(cur - arr[cur])
        return False

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
#         n = len(arr);
        
#         visited = [False for _ in range(n)];
        
#         def helper(i):
#             if  i < 0 or i > n-1 or visited[i]:
#                 return False;
#             if arr[i] == 0:
#                 return True;
            
#             visited[i] = True;
            
#             right = helper(i+arr[i]);
#             left  = helper(i-arr[i]);
            
#             visited[i] = False;
            
#             if right or left:
#                 return True;
#             return False;
        
#         return helper(start);

        if not arr:
            return False;
        if arr[start] == 0:
            return True;
        queue = [start];
        n = len(arr);
        visited = [False for _ in range(n)];
        
        while queue:
            index = queue.pop(0);
            visited[index] = True;
            newIndices = [index - arr[index], index + arr[index]];
            
            for i in newIndices:
                if i>=0 and i<n and not visited[i]:
                    queue.append(i);
                    if arr[i] == 0:
                        return True;
        return False;
            
            
        


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        visited = set()
        q = [start]
        while q:
            q = [i for x in q for i in (x - arr[x], x + arr[x]) if 0 <= i < len(arr) and i not in visited]
            for i in q:
                if arr[i] == 0: return True
                visited.add(i)
        return False

class Solution:
    visited = set()
    def canReach(self, arr: List[int], start: int) -> bool:
        visited = set()
        return self.backtrack(arr, start, visited)
    
    def backtrack(self, arr, index, visited):
        if index < 0 or index >= len(arr) or arr[index] < 0:
            return False
        if arr[index] == 0:
            return True
        temp = arr[index]
        arr[index] *= -1
        return self.backtrack(arr, index + temp, visited) or self.backtrack(arr, index - temp, visited)

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
#         n = len(arr);
        
#         visited = [False for _ in range(n)];
        
#         def helper(i):
#             if  i < 0 or i > n-1 or visited[i]:
#                 return False;
#             if arr[i] == 0:
#                 return True;
            
#             visited[i] = True;
            
#             right = helper(i+arr[i]);
#             left  = helper(i-arr[i]);
            
#             visited[i] = False;
            
#             if right or left:
#                 return True;
#             return False;
        
#         return helper(start);


        

        n = len(arr);
        if n==0:
            return False;
        if arr[start] == 0:
            return True;
        queue = [start];
        visited = [False for _ in range(n)];
        
        while queue:
            index = queue.pop(0);
            visited[index] = True;
            
            right = index + arr[index];
            left = index - arr[index];
            
            if right < n and not visited[right]:
                if arr[right] == 0:
                    return True;
                queue.append(right);
            
            if left >=0 and not visited[left]:
                if arr[left] == 0:
                    return True;
                queue.append(left);
            
        return False;
        


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        from collections import defaultdict
        graph=defaultdict(list)
        length=len(arr)
        for i in range(len(arr)):
            if arr[i]!=0:
                if i-arr[i]>=0:
                    graph[i].append(i-arr[i])
                if i+arr[i]<length:
                    graph[i].append(i+arr[i])
        zeroindex=[i for i,j in enumerate(arr) if j==0]
        visited=[]
        print(graph,zeroindex)
        def dfs(s,visited):
            if s in zeroindex:
                return True
            if s in visited:
                return False
            visited.append(s)
            for i in graph[s]:
                if dfs(i,visited):
                    return True
            return False
        return dfs(start,visited)

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        def dfs(start, count):
            if start < 0 or start >=len(arr):
                return False
            if count >= len(arr):
                return False
            if not arr[start]:
                return True
            return dfs(arr[start]+start, count+1) or dfs(start-arr[start], count+1)
        return dfs(start, 0)

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        graph = collections.defaultdict(set)
        for i in range(n):
            if i+arr[i]<n:
                graph[i].add(i+arr[i])
            if i-arr[i]>=0:
                graph[i].add(i-arr[i])
        end = set([i for i in range(n) if arr[i]==0])
        
        q = [start]
        visited = set([start])
        
        while q:
            x = q.pop(0)
            for i in graph[x]:
                if i in end:
                    return True
                if i not in visited:
                    visited.add(i)
                    q.append(i)
                    
        return False


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


class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n=len(arr)
        q=[start]
        while q:
            node=q.pop(0)
            #print(arr[node])
            if arr[node]==0:
                return True
            if arr[node]<0:
                continue
            for i in [node+arr[node],node-arr[node]]:
                #print(i)
                if i>=0 and i<n:
                    q.append(i)
            #print(q)
            arr[node]=-arr[node]
            #print(arr)
        return False

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

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        # array to add to check values and to pop current values
        to_check = [start]
        
        
        while len(to_check) > 0:
            current = to_check.pop(0)
            if arr[current] == 0:
                return True
            if arr[current] < 0:
                continue
            
            for i in [current+arr[current], current-arr[current]]:
                if 0 <= i < len(arr):
                    to_check.append(i)
                    
            arr[current] = -1
        
        return False
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # change = 1
        # prevchange = 0
        # n = len(arr)
        # if arr[start] == 0:
        #     return True
        # while change != prevchange:
        #     prevchange = change
        #     for index, val in enumerate(arr):
        #         print(arr)
        #         # if val is 0 then skip
        #         if val != 0:
        #         # check the jump is within bounds
        #             if index + val < n and arr[index + val] == 0 and index != start:
        #                 arr[index] = 0
        #                 change += 1
        #             elif index - val > -1 and arr[index - val] == 0 and index != start:
        #                 arr[index] = 0
        #                 change += 1
        #             elif index + val < n and arr[index + val] == 0 and index == start:
        #                 return True
        #             elif index - val > -1 and arr[index - val] == 0 and index == start:
        #                 return True
        # return False