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 <stdbool.h>
2#include <stdlib.h>
3
4bool canReachHelper(int* arr, int arrSize, int start, bool* visited) {
5 if (start < 0 || start >= arrSize || visited[start])
6 return false;
7 if (arr[start] == 0)
8 return true;
9 visited[start] = true;
10 return canReachHelper(arr, arrSize, start + arr[start], visited) ||
11 canReachHelper(arr, arrSize, start - arr[start], visited);
12}
13
14bool canReach(int* arr, int arrSize, int start) {
15 bool* visited = (bool*)calloc(arrSize, sizeof(bool));
16 bool result = canReachHelper(arr, arrSize, start, visited);
17 free(visited);
18 return result;
19}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.
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#include <queue>
class Solution {
public:
bool canReach(std::vector<int>& arr, int start) {
std::queue<int> q;
std::vector<bool> visited(arr.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
if (arr[curr] == 0)
return true;
int nextPos = curr + arr[curr];
int prevPos = curr - arr[curr];
if (nextPos < arr.size() && !visited[nextPos]) {
visited[nextPos] = true;
q.push(nextPos);
}
if (prevPos >= 0 && !visited[prevPos]) {
visited[prevPos] = true;
q.push(prevPos);
}
}
return false;
}
};This C++ solution implements BFS using a queue to explore the array. Starting from the initial position, it progressively explores all reachable indices in both forward and backward directions, tracking visited positions with a vector. The BFS terminates when an accessible zero-value index is found.