Find Index of zero to be replaced to get maximum length of consecutive ones

Companies:
  • Google Interview Questions

Given an array containing only zeros and ones, find the index of zero to be replaced with one to get the maximum length of consecutive ones.

Test Case

Example Input : 1 0 0 1 0 1
Sample Output: 4

Test Case Explanation

If we replace zero located at index 1, the maximum length of consecutive1s will be 2, if we replace the zero located at index 2, then also the maximum length of consecutive 1s will be 2. If we replace the zero located at index 4, then the length of maximum 1s will be 3. Therefore, 4 is our answer.

Solution

The easiest way to solve this problem is to count the number of consecutive 1s to the left of a zero and the number of consecutive 1s to the right of a zero and add them. Add the above two numbers for all the zeros and pick the index which has maximum sum of these numbers.

If we implement the above algorithm in a naive way, then the time complexity would be O(n^2).

However, we can optimize the implementation of the above approach by using preprocessing.

Preprocessing

We will create an array leftof size n. left[i] for any given index i will store the no of consecutive 1s to the left of index i. Therefore, left[i] for any given index will either store 0 if i-1th element of the array is 0 or it will store left[i-1] + 1 if i-1th element is 1. Since there is no element to the left of 0 index, left[0] = 0

For the test case given above, the left array will contain 0 1 0 0 1 0

Similarly, we will create an array right of size n. right[i] for any given index i will store the no of consecutive 1s to the right of index i. Therefore, right[i] for any given index will either store 0 if the i+1th element of the array is 0 or it will store right[i+1] + 1 if the i+1th element is 1. Since there is no element to the right of n-1 index, right[n-1] = 0.

For the test case given above right array will contain 0 0 1 0 1 0

Once, we are done calculating left and right, we just have to find the index for which left[i] + right[i] is the maximum.

See the code below for the full implementation.

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> vec = {1, 0, 0, 1, 0, 1 };

    int n = vec.size();

    vector<int> left(n), right(n);

    left[0] = 0;
    for(int i = 1; i < n; i++) {
        if (vec[i-1] == 0) {
            left[i] = 0;
        }
        else {
            left[i] = left[i-1] + vec[i-1];
        }
    }

    right[n-1] = 0;
    for(int i = n - 2; i >= 0; i--) {
        if (vec[i + 1] == 0) {
            right[i] = 0;
        }
        else {
            right[i] = right[i + 1] + vec[i + 1];
        }
    }

    int ma = -1;
    int index = -1;
    for(int i = 0; i < n; i++) {
        if (vec[i] == 0) {
            int can = left[i] + right[i];
            if (can > ma) {
                ma = can;
                index = i;
            }
        }
    }

    cout << "0 to be replaced is at position " << index << "\n";
}
Scroll to Top