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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Graph traversal

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)
		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
			elif 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]
			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)


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)
		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


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:

	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):
			visited = [False] * len(arr)
			queue = []
			queue.append(s)
			visited[s] = True
			while queue:
				n = queue.pop(0)
				if arr[n] == d:
					return True
				for i in graph[n]:
					if visited[i] == False:
						queue.append(i)
						visited[i] = True
			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:
		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
			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))
	print(Solution().canReach([3, 0, 2, 1, 2], 2))


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
		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])
		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:
		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:

		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
		return rcrs(start)

	def canReach(self, arr: List[int], start: int) -> bool:
		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])
				q.append(i - arr[i])
		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:
		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:
		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:
		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:
		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