1306

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.