# Jump Game III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/jump-game-iii)
Canonical: https://scaleengineer.com/dsa/problems/jump-game-iii
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array
**Companies:** [Snap](https://scaleengineer.com/companies/snap), [Pinterest](https://scaleengineer.com/companies/pinterest), [Tanium](https://scaleengineer.com/companies/tanium)
---
## Problem
Given an array of non-negative integers `arr`, you are initially positioned at `start` index of the array. When you are at index `i`, you can jump to `i + arr[i]` or `i - arr[i]`, check if you can reach **any** index with value 0.

Notice that you can not jump outside of the array at any time.

**Example 1:**

**Input:** arr = [4,2,3,0,3,1,2], start = 5
**Output:** true
**Explanation:** 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 

**Example 2:**

**Input:** arr = [4,2,3,0,3,1,2], start = 0
**Output:** true 
**Explanation:** 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

**Example 3:**

**Input:** arr = [3,0,2,1,2], start = 2
**Output:** false
**Explanation:** There is no way to reach at index 1 with value 0.

**Constraints:**

* `1 <= arr.length <= 5 * 104`
* `0 <= arr[i] < arr.length`
* `0 <= start < arr.length`

# Approaches
## Recursive DFS with Visited Set
This approach models the problem as a graph traversal. The array indices are the nodes, and the possible jumps define the edges. We use Depth-First Search (DFS) to explore all reachable indices from the `start` index. To prevent getting stuck in infinite loops (cycles), we use an auxiliary boolean array `visited` to keep track of the indices we have already explored.
**Time:** O(N), where N is the length of the array. Each index is visited at most once. · **Space:** O(N). This is composed of O(N) for the `visited` array and O(N) for the recursion call stack in the worst-case scenario (e.g., a long chain of jumps).
**Pros:** Conceptually simple and directly translates the problem's recursive nature.; Correctly handles cycles.
**Cons:** Can lead to a `StackOverflowError` for very deep recursion paths (long chains of jumps).; Uses extra space for both the `visited` array and the recursion stack.
### Explanation
The algorithm starts a recursive traversal from the `start` index.
A `visited` array of the same size as the input array `arr` is initialized to all `false`.
The recursive function `canReachRecursive(currentIndex, arr, visited)` works as follows:
1.  **Base Case (Out of Bounds):** If `currentIndex` is less than 0 or greater than or equal to `arr.length`, it's an invalid jump. Return `false`.
2.  **Base Case (Already Visited):** If `visited[currentIndex]` is `true`, we have already been at this index. To avoid a cycle, we return `false`.
3.  **Base Case (Target Found):** If `arr[currentIndex]` is 0, we have reached a target index. Return `true`.
4.  **Mark as Visited:** Set `visited[currentIndex] = true` to mark that we are currently exploring from this index.
5.  **Recursive Step:** Explore the two possible jumps:
    *   Jump forward: `canReachRecursive(currentIndex + arr[currentIndex], arr, visited)`
    *   Jump backward: `canReachRecursive(currentIndex - arr[currentIndex], arr, visited)`
6.  If either of the recursive calls returns `true`, it means a path to a 0 exists, so we return `true`. Otherwise, return `false`.
The main function initializes the `visited` array and calls the recursive function with the `start` index.

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

    private boolean canReachRecursive(int[] arr, int index, boolean[] visited) {
        // Base case: out of bounds
        if (index < 0 || index >= arr.length) {
            return false;
        }
        // Base case: already visited
        if (visited[index]) {
            return false;
        }
        // Base case: target found
        if (arr[index] == 0) {
            return true;
        }

        // Mark as visited
        visited[index] = true;

        // Recursive step
        boolean found = canReachRecursive(arr, index + arr[index], visited) ||
                        canReachRecursive(arr, index - arr[index], visited);

        return found;
    }
}
```
### Algorithm
1. Initialize a boolean array `visited` of size `arr.length` to all `false`.
2. Define a recursive function `dfs(index)`:
   a. If `index` is out of bounds or `visited[index]` is true, return `false`.
   b. If `arr[index] == 0`, return `true`.
   c. Mark `visited[index] = true`.
   d. Explore right: `foundRight = dfs(index + arr[index])`.
   e. Explore left: `foundLeft = dfs(index - arr[index])`.
   f. Return `foundRight || foundLeft`.
3. Call `dfs(start)` and return its result.

## Iterative BFS with Visited Set
This approach also treats the problem as a graph reachability problem but uses Breadth-First Search (BFS) instead of DFS. BFS explores the graph layer by layer, which is useful for finding the shortest path (though not required here). An iterative implementation using a queue avoids the risk of stack overflow. We still need a `visited` set to handle cycles.
**Time:** O(N), where N is the length of the array. Each index is enqueued and dequeued at most once. · **Space:** O(N). This is composed of O(N) for the `visited` array and O(W) for the queue, where W is the maximum width of the graph. In the worst case, W can be O(N).
**Pros:** Avoids recursion and the risk of `StackOverflowError`.; Generally more robust for very large or deep graphs compared to recursive DFS.
**Cons:** Still requires O(N) extra space for the `visited` array.
### Explanation
The algorithm uses a queue to manage the indices to visit.
It starts by adding the `start` index to the queue and marking it as visited.
The algorithm then enters a loop that continues as long as the queue is not empty.
In each iteration, it dequeues an index `currentIndex`.
If `arr[currentIndex]` is 0, the target is found, and the function returns `true`.
Otherwise, it calculates the two possible next indices: `currentIndex + arr[currentIndex]` and `currentIndex - arr[currentIndex]`.
For each next index, it checks if it's within the array bounds and has not been visited yet. If both conditions are met, the index is added to the queue and marked as visited.
If the loop completes without finding an index with value 0, it means no such index is reachable, and the function returns `false`.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();

        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int index = queue.poll();

            if (arr[index] == 0) {
                return true;
            }

            // Jump forward
            int nextIndexForward = index + arr[index];
            if (nextIndexForward < n && !visited[nextIndexForward]) {
                queue.add(nextIndexForward);
                visited[nextIndexForward] = true;
            }

            // Jump backward
            int nextIndexBackward = index - arr[index];
            if (nextIndexBackward >= 0 && !visited[nextIndexBackward]) {
                queue.add(nextIndexBackward);
                visited[nextIndexBackward] = true;
            }
        }

        return false;
    }
}
```
### Algorithm
1. Initialize a boolean array `visited` of size `arr.length` to all `false`.
2. Initialize a queue `q` and add `start` to it.
3. Mark `visited[start] = true`.
4. While `q` is not empty:
   a. Dequeue an index `curr = q.poll()`.
   b. If `arr[curr] == 0`, return `true`.
   c. Calculate next indices: `nextRight = curr + arr[curr]` and `nextLeft = curr - arr[curr]`.
   d. If `nextRight` is valid (in bounds and not visited), add it to `q` and mark it as visited.
   e. If `nextLeft` is valid (in bounds and not visited), add it to `q` and mark it as visited.
5. If the loop finishes, return `false`.

## BFS with In-place Marking
This is the most space-efficient approach. It's based on the BFS algorithm but cleverly avoids using a separate `visited` array. Instead, it modifies the input array `arr` itself to mark indices as visited. Since all values in `arr` are non-negative, we can mark an index `i` as visited by changing `arr[i]` to a negative value. This eliminates the need for an O(N) auxiliary data structure for tracking visited nodes.
**Time:** O(N). Each index is visited and processed at most once. · **Space:** O(W), where W is the maximum width of the graph. In the worst case, this can be O(N). This is an improvement over the previous approaches as we no longer need the separate O(N) `visited` array. The space is dominated by the queue.
**Pros:** Most space-efficient solution.; Avoids recursion and potential stack overflow.
**Cons:** Modifies the input array, which might not be permissible in all contexts.
### Explanation
The algorithm proceeds like a standard BFS using a queue.
When an index `currentIndex` is dequeued, we first check if it's valid and not visited. An index is considered visited if its value `arr[currentIndex]` is negative. If it's invalid or visited, we skip it.
If `arr[currentIndex]` is 0, we've found the target and return `true`.
To mark the index as visited and prevent re-processing, we negate the value at that index: `arr[currentIndex] = -arr[currentIndex]`. Before doing this, we store the original jump value.
The logic for exploring neighbors (jumping forward and backward) remains the same, but we use the original jump value (stored before negation).
This method modifies the input array. If the problem constraints required preserving the original array, this approach would be invalid, or we would need to restore the array's values before returning.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int index = queue.poll();

            if (index < 0 || index >= n || arr[index] < 0) {
                continue;
            }

            if (arr[index] == 0) {
                return true;
            }

            int jump = arr[index];
            // Mark as visited by negating
            arr[index] = -arr[index];

            queue.add(index + jump);
            queue.add(index - jump);
        }

        return false;
    }
}
```
### Algorithm
1. Initialize a queue `q` and add `start` to it.
2. While `q` is not empty:
   a. Dequeue an index `curr = q.poll()`.
   b. If `curr` is out of bounds or `arr[curr]` is negative (already visited), continue.
   c. If `arr[curr] == 0`, return `true`.
   d. Get jump distance: `jump = arr[curr]`.
   e. Mark as visited: `arr[curr] = -arr[curr]`.
   f. Enqueue `curr + jump` and `curr - jump`.
3. If the loop finishes, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean canReach(int[] arr, int start) {
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(start);
    while (!q.isEmpty()) {
      int i = q.poll();
      if (arr[i] == 0) {
        return true;
      }
      int x = arr[i];
      arr[i] = -1;
      for (int j : List.of(i + x, i - x)) {
        if (j >= 0 && j < arr.length && arr[j] >= 0) {
          q.offer(j);
        }
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canReach(vector<int> &arr, int start) {
    queue<int> q{{start}};
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      if (arr[i] == 0) {
        return true;
      }
      int x = arr[i];
      arr[i] = -1;
      for (int j : {i + x, i - x}) {
        if (j >= 0 && j < arr.size() && ~arr[j]) {
          q.push(j);
        }
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool: q = deque([start]) while q: i = q . popleft() if arr[i] == 0: return True x = arr[i] arr[i] = - 1 for j in (i + x, i - x): if 0 <= j < len(arr) and arr[j] >= 0: q . append(j) return False

```