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.lengthIn #1306 Jump Game III, you are given an array and a starting index. From any position i, you can jump either to i + arr[i] or i - arr[i]. The goal is to determine whether you can reach any index containing 0.
A common way to approach this problem is by modeling the array as a graph where each index represents a node and the possible jumps form edges. Using either Depth-First Search (DFS) or Breadth-First Search (BFS), you explore reachable indices starting from the given index.
To prevent infinite loops, maintain a visited set or mark indices as visited. During traversal, ensure the next index stays within valid array bounds. If a node with value 0 is reached, the search can terminate early.
This graph traversal strategy ensures that each index is processed at most once, making the solution efficient for large arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS Traversal | O(n) | O(n) |
| DFS Traversal | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Think of BFS to solve the problem.
When you reach a position with a value = 0 then return true.
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.
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.
1#include <vector>
2#include <iostream>
3
4class Solution {
5public:
6 bool canReach(std::vector<int>& arr, int start) {
7 return dfs(arr, start);
8 }
9
10private:
11 bool dfs(std::vector<int>& arr, int pos) {
12 if (pos < 0 || pos >= arr.size() || arr[pos] < 0)
13 return false;
14 if (arr[pos] == 0)
return true;
int jump = arr[pos];
arr[pos] = -arr[pos]; // Mark as visited
bool result = dfs(arr, pos + jump) || dfs(arr, pos - jump);
arr[pos] = -arr[pos]; // Reset the marked value
return result;
}
};The C++ solution uses a depth-first search (DFS) method by altering the array to mark visited indices with negative values temporarily. The solution begins by checking base cases, and recursively explores each potential jump until reaching an index with a zero value.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of Jump Game problems frequently appear in technical interviews at large tech companies. This problem tests graph traversal concepts, boundary checks, and cycle detection using BFS or DFS.
A queue is typically used for BFS, while recursion or an explicit stack works for DFS. Additionally, a visited set or boolean array is important to ensure indices are not revisited and to prevent infinite loops.
The optimal approach is to treat the array as a graph and perform either BFS or DFS starting from the given index. By exploring reachable indices and marking them as visited, you avoid cycles and determine if any index with value 0 can be reached in O(n) time.
Without tracking visited indices, the traversal could repeatedly jump between the same positions and create infinite loops. A visited structure ensures each index is processed only once, improving both correctness and efficiency.
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.