Problem Description

You are given an array of non-negative integers called arr and an integer start. You are initially positioned at index start in the array. At every step, you can jump either to start + arr[start] or start - arr[start], as long as the destination index is within the bounds of the array (i.e., between 0 and arr.length - 1).

Your goal is to determine if you can reach any index with value 0 in arr, starting from start and following the jump rules above. You are not allowed to visit the same index more than once during your journey.

• Input: arr (an array of non-negative integers), start (an integer index)
• Output: Return true if you can reach any index with value 0, otherwise return false.
• Constraints: You must not reuse the same index in a single path.

Thought Process

At first glance, this problem appears similar to a maze or graph traversal problem. From each index, you have two possible moves: forward and backward by the value at that index. The main challenge is to avoid cycles—since you cannot revisit the same index, you need a way to track which indices you've already visited.

A brute-force approach would try all possible paths from the starting index, recursively exploring each jump. However, this could lead to repeated work and even infinite loops if cycles are not handled. To optimize, we should "mark" indices as visited (like coloring rooms in a maze) to prevent revisiting and unnecessary computation.

This leads us to classic traversal techniques—Depth-First Search (DFS) or Breadth-First Search (BFS)—where we systematically explore reachable indices while keeping track of those we've already checked.

Solution Approach

We can solve this problem using either DFS or BFS. The main steps are:

1. Initialization: Create a visited structure (like a boolean array or set) to record which indices have been checked.
2. Traversal: Starting from start, explore both possible jumps: i + arr[i] and i - arr[i].
3. Base Cases:
   • If the current index is out of bounds, return false.
   • If the value at the current index is 0, return true (success!).
   • If the index has been visited, return false to avoid cycles.
4. Mark Visited: Before jumping, mark the current index as visited.
5. Recursive/Iterative Search: For DFS, recursively call the function for both possible moves. For BFS, use a queue to process indices level by level.
6. Return Result: If any path leads to a zero, return true. If all paths are exhausted, return false.

We use a visited array (or set) because lookups and updates are O(1), ensuring efficiency and correctness.

Example Walkthrough

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

1. Start at index 5 (arr[5] = 1). Possible jumps: 5 + 1 = 6 and 5 - 1 = 4.
2. Jump to index 6 (arr[6] = 2). Possible jumps: 6 + 2 = 8 (out of bounds), 6 - 2 = 4.
3. Jump to index 4 (arr[4] = 3). Possible jumps: 4 + 3 = 7 (out of bounds), 4 - 3 = 1.
4. Jump to index 1 (arr[1] = 2). Possible jumps: 1 + 2 = 3, 1 - 2 = -1 (out of bounds).
5. Jump to index 3 (arr[3] = 0). Success! We reached a zero.

At each step, we mark indices as visited to avoid loops. The process stops as soon as a zero is found.

Time and Space Complexity

Brute-force: Without marking visited indices, the number of paths can grow exponentially (O(2^n)), as each index could branch into two more.

Optimized (DFS/BFS with visited):

• Time Complexity: O(n), since each index is visited at most once.
• Space Complexity: O(n), for the visited array (or set) and the recursion stack or BFS queue.

This is efficient and scales well even for large arrays.

Summary

The Jump Game III problem is a classic example of graph traversal on a 1D array. By recognizing the need to avoid cycles and redundant work, we use a visited structure and either DFS or BFS to explore all reachable indices. The solution is elegant because it transforms a potentially exponential search into a linear one, thanks to careful bookkeeping and systematic exploration.

Code Implementation

class Solution:
    def canReach(self, arr, start):
        n = len(arr)
        visited = [False] * n

        def dfs(i):
            if i < 0 or i >= n or visited[i]:
                return False
            if arr[i] == 0:
                return True
            visited[i] = True
            return dfs(i + arr[i]) or dfs(i - arr[i])

        return dfs(start)
      

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<bool> visited(n, false);
        return dfs(arr, start, visited);
    }
private:
    bool dfs(vector<int>& arr, int i, vector<bool>& visited) {
        if (i < 0 || i >= arr.size() || visited[i]) return false;
        if (arr[i] == 0) return true;
        visited[i] = true;
        return dfs(arr, i + arr[i], visited) || dfs(arr, i - arr[i], visited);
    }
};
      

class Solution {
    public boolean canReach(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        return dfs(arr, start, visited);
    }

    private boolean dfs(int[] arr, int i, boolean[] visited) {
        if (i < 0 || i >= arr.length || visited[i]) return false;
        if (arr[i] == 0) return true;
        visited[i] = true;
        return dfs(arr, i + arr[i], visited) || dfs(arr, i - arr[i], visited);
    }
}
      

var canReach = function(arr, start) {
    const n = arr.length;
    const visited = new Array(n).fill(false);

    function dfs(i) {
        if (i < 0 || i >= n || visited[i]) return false;
        if (arr[i] === 0) return true;
        visited[i] = true;
        return dfs(i + arr[i]) || dfs(i - arr[i]);
    }

    return dfs(start);
};