Problem Description

You are given an array arr of non-negative integers and a starting position start. Your goal is to determine if you can reach any index in the array that contains the value 0.

The movement rules are:

• You begin at index start
• When you are at index i, you can jump to either:
  • i + arr[i] (jump forward by arr[i] positions)
  • i - arr[i] (jump backward by arr[i] positions)
• You cannot jump outside the array boundaries

The problem asks you to return true if you can reach any index with value 0, and false otherwise.

For example, if arr = [4, 2, 3, 0, 3, 1, 2] and start = 5:

• From index 5 (value = 1), you can jump to index 4 or index 6
• From index 4 (value = 3), you can jump to index 1 or index 7 (but 7 is out of bounds)
• From index 1 (value = 2), you can jump to index 3 or go back to an already visited index
• Index 3 has value 0, so you can reach it and return true

The solution uses BFS (Breadth-First Search) to explore all reachable indices from the starting position. It marks visited indices by setting them to -1 to avoid revisiting them, which prevents infinite loops. The search continues until either an index with value 0 is found (returning true) or all reachable indices have been explored without finding a 0 (returning false).

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: This problem can be modeled as a graph where each index is a node, and edges exist from index i to indices i + arr[i] and i - arr[i]. We need to find if there's a path from the start node to any node with value 0.

Is it a tree?

• No: The graph structure is not a tree because:
  • There can be cycles (you might be able to return to a previously visited index through different paths)
  • Nodes can have multiple parents (multiple indices can jump to the same target index)
  • The structure doesn't have a hierarchical parent-child relationship

Is the problem related to directed acyclic graphs?

• No: The graph can contain cycles. For example, if arr = [1, 1], from index 0 you can jump to index 1, and from index 1 you can jump back to index 0, creating a cycle.

Is the problem related to shortest paths?

• No: We don't need to find the shortest path to a node with value 0. We only need to determine if ANY path exists to reach such a node.

Does the problem involve connectivity?

• Yes: The core question is about connectivity - whether we can reach (connect to) any index with value 0 from the starting index.

Does the problem have small constraints?

• Yes: The problem typically has reasonable array size constraints that allow for DFS/BFS exploration without timeout issues.

DFS/backtracking?

• Yes: DFS is perfectly suitable here. We can explore each possible jump recursively, marking visited nodes to avoid infinite loops, and return true as soon as we find any index with value 0.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this connectivity problem, which aligns perfectly with exploring all reachable indices from the starting position to find if we can reach any index containing 0.

Intuition

The key insight is to recognize that this is a graph traversal problem in disguise. Each index in the array represents a node, and from each index i, we can create directed edges to indices i + arr[i] and i - arr[i]. The question then becomes: can we traverse from the start node to any node that has value 0?

Think of it like exploring a maze where:

• You start at a specific position (start index)
• From each position, you have exactly two possible moves (forward or backward by the value at that position)
• Your goal is to reach any position marked with 0

Since we only care about finding ANY path to a 0 (not the shortest path), we can use either DFS or BFS to explore all reachable positions. The critical observation is that we need to avoid revisiting the same index to prevent infinite loops.

For example, if we're at index 2 with value 3, we might jump to index 5, then from index 5 we might eventually come back to index 2. Without marking visited indices, we'd be stuck in an endless cycle.

The solution naturally emerges:

1. Start exploring from the start index
2. For each position we visit, check if it contains 0 - if yes, we're done
3. Mark the current position as visited (the solution cleverly does this by setting arr[i] = -1)
4. Try both possible jumps (forward and backward) if they're within bounds and haven't been visited
5. Continue until we either find a 0 or exhaust all reachable positions

The BFS approach used in the solution ensures we explore positions level by level, but DFS would work equally well since we're not looking for the shortest path.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution implements a BFS (Breadth-First Search) traversal to explore all reachable indices from the starting position.

Data Structure: We use a deque (double-ended queue) to maintain the indices to be explored. The deque allows efficient addition and removal of elements from both ends, though in BFS we only need to append at the right and pop from the left.

Algorithm Steps:

1. Initialize the queue: Start by adding the start index to the queue.

   q = deque([start])

2. Process each index level by level: While the queue is not empty, extract the leftmost index i from the queue.

   i = q.popleft()

3. Check for target: If arr[i] == 0, we've found our target and return True immediately.

   if arr[i] == 0:
       return True

4. Mark as visited: Store the jump value x = arr[i], then mark the current index as visited by setting arr[i] = -1. This clever technique modifies the array in-place to track visited indices without using extra space for a separate visited set.

   x = arr[i]
   arr[i] = -1

5. Explore neighbors: Calculate the two possible jump destinations: i + x and i - x. For each destination j:

   • Check if it's within bounds: 0 <= j < len(arr)
   • Check if it hasn't been visited: arr[j] >= 0 (since visited indices are marked as -1)
   • If both conditions are met, add j to the queue for future exploration

   for j in (i + x, i - x):
       if 0 <= j < len(arr) and arr[j] >= 0:
           q.append(j)

6. Return result: If the queue becomes empty without finding any index with value 0, return False.

Why BFS works here:

• BFS guarantees that we explore all reachable indices systematically
• The visited marking prevents infinite loops
• As soon as we find any 0, we can return immediately (early termination)
• The level-by-level exploration ensures we don't miss any reachable position

Time Complexity: O(n) where n is the length of the array, as each index is visited at most once.

Space Complexity: O(n) for the queue in the worst case when all indices are reachable and added to the queue before finding a 0.

Example Walkthrough

Let's trace through a small example to illustrate the BFS solution approach.

Example: arr = [3, 0, 2, 1, 2], start = 2

Initial Setup:

• Queue: [2]
• Array: [3, 0, 2, 1, 2]

Step 1: Process index 2

• Dequeue: i = 2
• Check: arr[2] = 2 (not 0, continue)
• Store jump value: x = 2
• Mark visited: arr[2] = -1
• Array becomes: [3, 0, -1, 1, 2]
• Calculate jumps:
  • Forward: 2 + 2 = 4 (valid, arr[4] = 2 ≥ 0)
  • Backward: 2 - 2 = 0 (valid, arr[0] = 3 ≥ 0)
• Queue: [4, 0]

Step 2: Process index 4

• Dequeue: i = 4
• Check: arr[4] = 2 (not 0, continue)
• Store jump value: x = 2
• Mark visited: arr[4] = -1
• Array becomes: [3, 0, -1, 1, -1]
• Calculate jumps:
  • Forward: 4 + 2 = 6 (out of bounds, skip)
  • Backward: 4 - 2 = 2 (already visited, arr[2] = -1, skip)
• Queue: [0]

Step 3: Process index 0

• Dequeue: i = 0
• Check: arr[0] = 3 (not 0, continue)
• Store jump value: x = 3
• Mark visited: arr[0] = -1
• Array becomes: [-1, 0, -1, 1, -1]
• Calculate jumps:
  • Forward: 0 + 3 = 3 (valid, arr[3] = 1 ≥ 0)
  • Backward: 0 - 3 = -3 (out of bounds, skip)
• Queue: [3]

Step 4: Process index 3

• Dequeue: i = 3
• Check: arr[3] = 1 (not 0, continue)
• Store jump value: x = 1
• Mark visited: arr[3] = -1
• Array becomes: [-1, 0, -1, -1, -1]
• Calculate jumps:
  • Forward: 3 + 1 = 4 (already visited, arr[4] = -1, skip)
  • Backward: 3 - 1 = 2 (already visited, arr[2] = -1, skip)
• Queue: []

Result: Queue is empty and we never found a 0, so return False.

Wait, this seems wrong! Let's reconsider - we should have found the 0 at index 1.

Correction - Step 3 Revisited: Actually, from index 0 with value 3, we can jump to index 3. But let me check if we can reach index 1...

From start index 2:

• Jump to index 0 or 4
• From index 0 (value 3): can jump to index 3 (0+3) but not to index -3
• From index 4 (value 2): can jump to index 6 (out of bounds) or index 2 (already visited)
• From index 3 (value 1): can jump to index 4 (visited) or index 2 (visited)

We cannot reach index 1 with value 0! The function would correctly return False.

Alternative Example: arr = [4, 2, 3, 0, 3, 1, 2], start = 5

Step 1: Process index 5

• arr[5] = 1 (not 0)
• Mark visited, jump to indices 4 and 6
• Queue: [4, 6]

Step 2: Process index 4

• arr[4] = 3 (not 0)
• Mark visited, jump to indices 1 and 7 (7 out of bounds)
• Queue: [6, 1]

Step 3: Process index 6

• arr[6] = 2 (not 0)
• Mark visited, jump to indices 8 (out of bounds) and 4 (visited)
• Queue: [1]

Step 4: Process index 1

• arr[1] = 2 (not 0)
• Mark visited, jump to indices 3 and -1 (out of bounds)
• Queue: [3]

Step 5: Process index 3

• arr[3] = 0 - Found!
• Return True

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

Each index in the array is visited at most once. When we visit an index i, we mark it as visited by setting arr[i] = -1, which prevents it from being added to the queue again. Since the queue processes each reachable index exactly once and there are at most n indices in the array, the time complexity is O(n).

Space Complexity: O(n)

The space complexity comes from the queue used for BFS traversal. In the worst case, the queue could contain all reachable indices before processing begins, which could be up to n elements. Therefore, the space complexity is O(n). Note that we're modifying the input array in-place for marking visited indices, so no additional space is needed for tracking visited nodes.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Input Array Without Restoration

The Pitfall: The solution modifies the input array arr by marking visited indices with -1. This is a destructive operation that permanently changes the input data. If the caller needs to use the array after calling this function, they'll find it corrupted with -1 values.

Example of the Problem:

arr = [4, 2, 3, 0, 3, 1, 2]
start = 5
solution = Solution()
result = solution.canReach(arr, start)
print(arr)  # Output: [4, -1, 3, 0, -1, -1, -1] - array is modified!
# The original array is lost

Solution Approaches:

Option 1: Use a Separate Visited Set

def canReach(self, arr: List[int], start: int) -> bool:
    queue = deque([start])
    visited = set([start])  # Track visited indices separately
  
    while queue:
        current_index = queue.popleft()
      
        if arr[current_index] == 0:
            return True
      
        jump_distance = arr[current_index]
      
        for next_index in (current_index + jump_distance, current_index - jump_distance):
            if 0 <= next_index < len(arr) and next_index not in visited:
                visited.add(next_index)
                queue.append(next_index)
  
    return False

Option 2: Create a Copy of the Array

def canReach(self, arr: List[int], start: int) -> bool:
    arr_copy = arr.copy()  # Work with a copy to preserve original
    queue = deque([start])
  
    while queue:
        current_index = queue.popleft()
      
        if arr_copy[current_index] == 0:
            return True
      
        jump_distance = arr_copy[current_index]
        arr_copy[current_index] = -1
      
        for next_index in (current_index + jump_distance, current_index - jump_distance):
            if 0 <= next_index < len(arr_copy) and arr_copy[next_index] >= 0:
                queue.append(next_index)
  
    return False

2. Adding Visited Nodes to Queue Multiple Times

The Pitfall: If you mark an index as visited only when you pop it from the queue (instead of when you add it), the same index might be added to the queue multiple times from different paths, leading to redundant processing.

Incorrect Implementation:

def canReach(self, arr: List[int], start: int) -> bool:
    queue = deque([start])
    visited = set()
  
    while queue:
        current_index = queue.popleft()
      
        # Marking visited here is too late!
        if current_index in visited:
            continue
        visited.add(current_index)
      
        if arr[current_index] == 0:
            return True
      
        jump_distance = arr[current_index]
      
        for next_index in (current_index + jump_distance, current_index - jump_distance):
            if 0 <= next_index < len(arr):
                # This index might already be in the queue!
                queue.append(next_index)
  
    return False

Correct Implementation: Mark indices as visited when adding them to the queue:

def canReach(self, arr: List[int], start: int) -> bool:
    queue = deque([start])
    visited = set([start])  # Mark start as visited immediately
  
    while queue:
        current_index = queue.popleft()
      
        if arr[current_index] == 0:
            return True
      
        jump_distance = arr[current_index]
      
        for next_index in (current_index + jump_distance, current_index - jump_distance):
            if 0 <= next_index < len(arr) and next_index not in visited:
                visited.add(next_index)  # Mark as visited when adding to queue
                queue.append(next_index)
  
    return False

Why This Matters: The incorrect approach can lead to exponential time complexity in worst-case scenarios where multiple paths lead to the same indices, causing the same nodes to be processed repeatedly.