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

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 consecutive`1s` 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 `left`of size `n`. `left[i]` for any given index `i` will store the no of consecutive `1`s 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-1`th element is `1`. Since there is no element to the left of `0` index, `left = 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 `1`s to the right of index `i`. Therefore, `right[i]` for any given index will either store `0` if the `i+1`th element of the array is 0 or it will store `right[i+1] + 1` if the `i+1`th 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;
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";
}
```
[gravityforms id="5" description="false" titla="false" ajax="true"]