Sponsored
Sponsored
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)
15 return true;
16 int jump = arr[pos];
17 arr[pos] = -arr[pos]; // Mark as visited
18 bool result = dfs(arr, pos + jump) || dfs(arr, pos - jump);
19 arr[pos] = -arr[pos]; // Reset the marked value
20 return result;
21 }
22};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
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.