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
- code
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
q = [start]
while q:
cur_i = q.pop() # pop() is dfs, pop(0) only is not bfs
if arr[cur_i] == 0: return True
if arr[cur_i] > 0:
# check available next steps
if cur_i + arr[cur_i] < len(arr):
q.append(cur_i + arr[cur_i])
if cur_i - arr[cur_i] >= 0:
q.append(cur_i - arr[cur_i])
# mark as visited
arr[cur_i] = -arr[cur_i]
return False
- code
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
changed = True
while changed:
changed = False
for i in range(len(arr)):
if arr[i] != 0 and ((i+arr[i] < len(arr) and arr[i+arr[i]] == 0) or (i-arr[i] >= 0 and arr[i-arr[i]] == 0)):
arr[i] = 0
changed = True
for i in range(len(arr)-1, -1, -1):
if arr[i] != 0 and ((i+arr[i] < len(arr) and arr[i+arr[i]] == 0) or (i-arr[i] >= 0 and arr[i-arr[i]] == 0)):
arr[i] = 0
changed = True
if arr[start] == 0: return True
return False
- code BFS TLE, no need to start from end, you will find all potential good start with this method.
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
reach = [i for i in range(len(arr)) if arr[i] == 0]
visited = set(reach)
q = deque(reach)
while q:
cur_i = q.popleft()
if cur_i == start: return True
# go left
i = cur_i - 1
while i >= 0:
if i not in visited and cur_i - i == arr[i]:
visited.add(i)
q.append(i)
i -= 1
# go right
i = cur_i + 1
while i < len(arr):
if i not in visited and i - cur_i == arr[i]:
visited.add(i)
q.append(i)
i += 1
return False