Description
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.length
Solutions
This solution implements a breadth-first search (BFS) approach to explore all indices reachable from the starting position. It maintains a seen set to prevent revisiting indices and avoid infinite loops. In each iteration of the outer while loop, it processes all indices in the current layer (using a for...of loop) and jumps to adjacent indices by either subtracting or adding the current value (cur - arr[cur] and cur + arr[cur]). New unvisited indices are collected in the next array, which becomes the stack for the next layer. The function returns true as soon as it finds an index with value 0, or false if all reachable positions are exhausted.
/**
* @param {number[]} arr
* @param {number} start
* @return {boolean}
*/
var canReach = function(arr, start) {
let stack = [start];
const seen = new Set();
seen.add(start);
while (stack.length > 0) {
next = [];
for (const cur of stack) {
if (arr[cur] === 0) {
return true;
}
const back = cur - arr[cur];
if (back >= 0 && !seen.has(back)) {
seen.add(back);
next.push(back);
}
const forw = cur + arr[cur];
if (forw < arr.length && !seen.has(forw)) {
seen.add(forw);
next.push(forw);
}
}
stack = next;
}
return false;
};