1306. Jump Game III

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