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

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.

1