1306. Jump Game III

Python

First try, time limit exceed

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        self.upbound = len(arr)-1
        if not arr:
            return False
        return self._travel(arr, [], start)

    def _travel(self, arr, visited, current):
        if current in visited:
            return False

        if current > self.upbound or current < 0:
            return False

        if arr[current] == 0:
            return True

        visited.append(current)

        return self._travel(arr, visited, current - arr[current]) \
            or self._travel(arr, visited, current + arr[current])

Second Try, BFS with queue

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

        upbound = len(arr)
        queue = [start]
        visited = set([start])

        while queue:
            current = queue.pop(0)

            if arr[current] == 0:
                return True

            left = current - arr[current]
            right = current + arr[current]

            if left >= 0 and left < upbound and left not in visited:
                visited.add(left)
                queue.append(left)

            if right >= 0 and right < upbound and right not in visited:
                visited.add(right)
                queue.append(right)

        return False

Python​

Python