Question

Given an array consisting of zeros and ones, you are allowed to flip at most 1 element from 0 to 1. Print the size of the sub array which consists of maximum number of consecutive 1's. Input Format: The first input denotes the array size. The remaining input denotes the array elements consisting of O's and 1's. Output Format: Print the count of maximum consecutive 1's. Sample Input: 10 1 0 1 1 1 0 1 1 1 0 Sample Output: 7.​

Answer 1

Answer:

VERIFIED ANSWER

Explanation:

A Simple Solution is to consider every subarray by running two loops. For every subarray, count number of zeroes in it. Return the maximum size subarray with m or less zeroes. Time Complexity of this solution is O(n2).

A Better Solution is to use auxiliary space to solve the problem in O(n) time.

For all positions of 0’s calculate left[] and right[] which defines the number of consecutive 1’s to the left of i and right of i respectively. 

For example, for arr[] = {1, 1, 0, 1, 1, 0, 0, 1, 1, 1} and m = 1, left[2] = 2 and right[2] = 2, left[5] = 2 and right[5] = 0, left[6] = 0 and right[6] = 3.

left[] and right[] can be filled in O(n) time by traversing array once and keeping track of last seen 1 and last seen 0. While filling left[] and right[], we also store indexes of all zeroes in a third array say zeroes[]. For above example, this third array stores {2, 5, 6}

Now traverse zeroes[] and for all consecutive m entries in this array, compute the sum of 1s that can be produced. This step can be done in