Problem Breakdown
We need to determine if a specific target condition (finding an index where arr[i] == 0) is reachable from a given starting position. The array defines the graph structure, where each index represents a node and its value determines valid outgoing edges (i + arr[i] or i - arr[i]).
Inputs:
arr: List of non-negative integers representing jump lengths at each index.start: Integer indicating the initial current position (index).
Outputs:
- Boolean: Returns
Trueif any reachable index contains 0, otherwise returnsFalse.
Implicit Constraints & Edge Cases:
- Cycles: Since jumps can be reversible or form loops (e.g., A -> B and B -> A), we must track visited indices to prevent infinite processing.
- Bounds: Jumps cannot take us outside the array indices
[0, len(arr) - 1]. - Immediate Target: If
arr[start] == 0, returnTrueimmediately without further traversal logic (handled naturally by checking current node). - No Path: It is possible that all reachable components do not contain a zero value.
Intuition
This problem can be modeled as finding if there exists a path from the start node to any node with weight 0 in an unweighted directed graph. A brute-force recursive approach would risk hitting recursion depth limits or Time Limit Exceeded (TLE) due to exponential paths without state tracking ().
The key insight is recognizing this as a graph reachability problem. We need to explore all reachable components from start. Since edge weights don’t matter for existence, Breadth-First Search (BFS) or Depth-First Search (DFS) are optimal choices. To ensure efficiency and avoid TLE:
- Use a
visitedset to mark indices we have already processed. This prevents cycles and redundant work, ensuring each node is touched at most once (). - Implement an iterative approach using a stack or queue instead of deep recursion to handle Python’s default recursion limit safely on large inputs (up to ).
Approach
- Initialize a set
visitedand add thestartindex. Addstartto our traversal structure (stack). - While the stack is not empty:
- Pop an index
curr_idx. - Check if
arr[curr_idx] == 0. If yes, returnTrue. - Calculate potential next indices based on jump rules:
next = curr + arr[curr]andprev = curr - arr[curr].
- Pop an index
- For each calculated neighbor:
- Verify it is within array bounds (
>= 0and< len(arr)). - If valid AND not in
visited: add to stack, mark as visited immediately (to prevent re-adding).
- Verify it is within array bounds (
- If the loop completes without finding a zero, return
False.
Complexity Analysis
- Time: where is the length of
arr. Each index enters and leaves the traversal structure at most once due to thevisitedset check before pushing neighbors. Operations per node are constant time (). - Space: . In the worst case, we store all indices in our stack/queue and visited set (e.g., a linear chain of jumps or disconnected components filling memory).
Solution
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
n = len(arr)
# Use iterative DFS to avoid recursion depth issues on large inputs.
stack = [start]
visited = {start}
while stack:
curr_idx = stack.pop()
# Check if current position is the target value 0
if arr[curr_idx] == 0:
return True
# Calculate possible jumps from current index
next_indices = [curr_idx + arr[curr_idx], curr_idx - arr[curr_idx]]
for nxt in next_indices:
# Check bounds and visited status before processing
if 0 <= nxt < n and nxt not in visited:
stack.append(nxt)
visited.add(nxt)
return False
Edge Cases Handled
- Start at Zero: The check
if arr[curr_idx] == 0handles the case where we start on a zero immediately or reach it later. - Cycles/Loops: The
visitedset ensures that if we jump back to an index already processed, it is skipped, preventing infinite recursion or loops. - Out of Bounds Jumps: Explicit bounds checking (
0 <= nxt < n) prevents accessing invalid memory indices before the loop continues. - No Zero Reachable: If the stack empties and no zero was found during traversal, the function correctly returns
False.