Can Fixed-Length Jumps Reach a Zero?
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Begin at index start of the nonnegative array arr. From index i, the next jump must land at i+arr[i] or i-arr[i], and must stay inside the array. Return whether some reachable index contains 0.
```cpp
class Solution {
public:
bool canReach(vector<int>& arr, int start);
};
```
### Examples
**Example 1:**
```text
Input: arr = [1,0,2], start = 0
Output: true
Explanation: Jump from index0 to index1, whose value is0.
```
**Example 2:**
```text
Input: arr = [2,0,2], start = 0
Output: false
Explanation: Only indices0 and2 are reachable; they jump between each other and cannot reach index1.
```
### Constraints
- The array contains 1 to 50000 elements.
- Each value satisfies `0 <= arr[i] < arr.length`.
- start is a valid array index.
### Contract considerations
Return a boolean without changing the native array interface.
```hint Read the boundary condition
Consider a starting zero, jumps that leave the array, and routes that revisit indices.
```
### Boundary reminders
Return a boolean without changing the native array interface.
Overview: Can Fixed-Length Jumps Reach a Zero?. Begin at index start of the nonnegative array arr. From index i, the next jump must land at i+arr[i] or i-arr[i], and must stay inside the array.