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 * 1040 <= arr[i] < arr.length0 <= start < arr.lengthProblem Overview: You are given an array arr and a starting index start. From index i, you can jump to i + arr[i] or i - arr[i]. The goal is to determine whether you can reach any index whose value is 0. The array behaves like a graph where each index is a node and jumps create edges.
The core challenge is avoiding infinite loops. Since jumps can revisit the same index repeatedly, the solution must track visited positions while exploring reachable indices.
Approach 1: Depth-First Search (DFS) (Time: O(n), Space: O(n))
Treat the array as a graph and explore it using recursion or an explicit stack. Start at the given index and recursively attempt both possible jumps: i + arr[i] and i - arr[i]. Maintain a visited set (or mark elements in-place) to prevent revisiting indices, which would otherwise create cycles. Each index is processed at most once, so the traversal runs in linear time. DFS works well because you only need to check reachability, not the shortest path. If any recursive path reaches an index with value 0, return true immediately.
This approach highlights the connection between arrays and graph traversal problems. You systematically explore neighbors while enforcing boundary checks (0 ≤ index < n) and skipping already visited nodes.
Approach 2: Breadth-First Search (BFS) (Time: O(n), Space: O(n))
BFS explores indices level by level using a queue. Start by pushing the start index into the queue. At each step, pop an index and check if its value is 0. If not, compute the two reachable indices and push valid, unvisited ones into the queue. Mark them as visited immediately to avoid duplicates.
BFS guarantees each index enters the queue at most once, giving the same O(n) time complexity. The space complexity is also O(n) due to the queue and visited tracking. This approach is often easier to reason about iteratively and mirrors standard graph traversal patterns used in many interview problems.
Both DFS and BFS rely on the same insight: the array forms an implicit graph where edges represent legal jumps. Efficient traversal requires marking visited nodes to avoid cycles.
Recommended for interviews: Either DFS or BFS is acceptable since both achieve optimal O(n) time complexity. DFS is slightly shorter to implement recursively, while BFS demonstrates explicit graph traversal skills. Interviewers mainly look for two things: recognizing the problem as a graph reachability problem and preventing infinite loops with a visited structure. Practicing both approaches strengthens understanding of Depth-First Search, Breadth-First Search, and graph-style traversal on an array.
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.
In this C implementation, a helper function canReachHelper is defined to handle recursion and keep track of visited indices using an array. If we reach a position with value 0, we return true. Otherwise, the recursion explores possible jumps both forward and backward. Memory for the visited array is allocated and freed appropriately to avoid memory leaks.
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.
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.
Here's how the C solution works: A queue is dynamically created and used to explore all potential positions, marking indices as visited in a dedicated boolean array. By processing each queue element, we're checking both forward and backward jumps. This approach terminates when an index with a zero value is found or when the queue is empty.
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.
We can use BFS to determine whether we can reach the index with a value of 0.
Define a queue q to store the currently reachable indices. Initially, enqueue the start index.
When the queue is not empty, take out the front index i of the queue. If arr[i] = 0, return true. Otherwise, mark the index i as visited. If i + arr[i] and i - arr[i] are within the array range and have not been visited, enqueue them and continue searching.
Finally, if the queue is empty, it means that we cannot reach the index with a value of 0, so return false.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) | Time Complexity: O(n), where n is the length of the array, because every index is visited at most once. |
| Breadth-First Search (BFS) | Time Complexity: O(n), as all reachable indices are visited. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(n) | O(n) | When recursive traversal is preferred and you want a concise reachability check |
| Breadth-First Search (BFS) | O(n) | O(n) | When you prefer iterative traversal using a queue or want clearer control over exploration order |
Jump Game III | Live Coding with Explanation | Leetcode - 1306 • Algorithms Made Easy • 8,257 views views
Watch 9 more video solutions →Practice Jump Game III with our built-in code editor and test cases.
Practice on FleetCode