1306. Jump Game III

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 to any index with value 0.

Notice that you can not jump outside of the array at any time.

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        if(!arr[start]) return true;

        int sz = arr.size();
        vector<bool> v(sz, false);
        queue<int> q;
        q.push(start);
        v[start] = true;
        while(!q.empty()) {
            int pos = q.front();
            q.pop();
            int left = pos - arr[pos], right = pos + arr[pos];
            if(left >= 0 && !v[left]) {
                if(!arr[left]) return true;
                v[left] = true;
                q.push(left);
            }
            if(right < sz && !v[right]) {
                if(!arr[right]) return true;
                v[right] = true;
                q.push(right);
            }
        }
        return false;
    }
};