O(n) C++ solution using greedy approach


#1
bool checkFarthestBulb(vector<int>& A, int& index, int B) {
    // Check whether a valid bulb exists to the right side
    int i = index + B - 1;
    if (i >= A.size()) {
        i = A.size() - 1;
    }
    
    while (A[i] != 1 && i > index) {
        i--;
    }
    if (i == index && A[i] == 0) {
        i--;
        // No bulb available on the right side, check on the left side
        while (i >= index - B + 1) {
            if (A[i] == 1) {
                // Got bulb on the left side, update the next index to be searched.
                index = i + B;
                return true;
            }
            i--;
        } 
        // Couldn't find any valid bulb on any of the sides.
        return false;
    } else {
        // Got bulb on the right side, update the next index to be searched.
        index = i + B;
        return true;
    }
    
}


int Solution::solve(vector<int> &A, int B) {
    int minBulbs = 0;
    int i = 0;
    while (i < A.size()) {
        if (checkFarthestBulb(A, i, B)) {
            minBulbs++;
        } else {
            return -1;
        }
    }
    return minBulbs;
}