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.lengthThis 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Jump Game - Greedy - Leetcode 55 • NeetCode • 290,114 views views
Watch 9 more video solutions →Practice Jump Game III with our built-in code editor and test cases.
Practice on FleetCode