< Back




1306. Jump Game III

We're given an array of non-negative integers and a starting location (index) within the array.
We're asked to find out if we can reach an index where the value of arr[index] is 0. We can only
move in two different ways at each index, i + arr[i] or i - arr[i].

With this, we use BFS starting from the start index. We inspect our two neighbors at each index,
i + arr[i], i - arr[i], validating if the index is within the bounds of the array and hasn't already
been visited. If we find an index with a value of 0, we return True. If we've exhausted all possible
paths and haven't found a 0, we return False.

The solution is as follows:


  class Solution:
      def canReach(self, arr: List[int], start: int) -> bool:
          n = len(arr)
          seen = {start}
          queue = [start]

          while queue:  
              curr_queue, queue = queue, []

              for i in curr_queue:
                  if arr[i] == 0:
                      return True

                  for neighbor in [i + arr[i], i - arr[i]]:
                      if neighbor not in seen and -1 < neighbor < n:
                          seen.add(neighbor)
                          queue.append(neighbor)

          return False


_ Time Complexity:

  O(n) - The time complexity of BFS is O(n), where n is the number of integers in the input.

_ Space Complexity:

  O(n) - We store the visited indices in a set, and the nodes to visit in a queue.