Sponsored
Sponsored
This approach employs DFS for exploring each possible path starting from the given start index. You recursively explore both forward and backward jumps, marking indices as visited to avoid cycles. If you reach an index with a value of 0, return true. If all paths are exhausted without finding a zero, return false.
Time Complexity: O(n), where n is the length of the array, because every index is visited at most once.
Space Complexity: O(n) due to the recursion stack and the visited array.
1class Solution:
2 def canReach(self, arr: list[int], start: int) -> bool:
3 def dfs(pos: int) -> bool:
4 if pos < 0 or pos >= len(arr) or arr[pos] < 0:
5 return False
6 if arr[pos] == 0:
7 return True
8 jump = arr[pos]
9 arr[pos] = -arr[pos] # Mark as visited
10 result = dfs(pos + jump) or dfs(pos - jump)
11 arr[pos] = -arr[pos] # Reset
12 return result
13 return dfs(start)The Python solution also uses a DFS approach similar to other implementations. Instead of a separate visited list, it marks visited indices directly in the array by negating the values. The recursive function dfs checks bounds, performs the value check, and makes recursive calls to explore each possible jump path.
This approach adopts a BFS strategy to explore all reachable indices from the starting point iteratively. Using a queue, enqueue all possible jump indices from a given position if they haven't been visited yet. Pop indices from the queue, and for each pop, check whether the position contains a zero, marking indices visited as you go.
Time Complexity: O(n), as all reachable indices are visited.
Space Complexity: O(n), given the storage requirements for the queue and the visited array.
1
The Python solution uses a deque to manage the exploration queue, marking indices as visited in an auxiliary boolean list. By iterating over the two possible jumps from each current index, the solution entirely embodies a typical BFS workflow.