Find maximum length sequence of continuous ones

Given a binary array, find the index of 0 to be replaced with 1 to get maximum length sequence of continuous ones.

 

For example,


Consider the array { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 }.
The index to be replaced is 7 to get continuous sequence of length 6 containing all 1’s.

 

The idea is very simple. We update each non-zero elements of array with count of their adjacent consecutive 1’s. For example, array { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 } is converted to { 0, 0, 1, 0, 3, 3, 3, 0, 2, 2 }. Now the problem reduces to finding the index of 0 whose sum of left and right element is maximum.

 

Below is C and Java implementation of the same. Note that this approach will modify the array and at-least requires two traversals of the array. We can use an auxiliary array to avoid modification of original array or restore the original array before returning.

C

Download   Run Code

Java

Download   Run Code



Output:


Index to be replaced is 7

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
We have discussed two more approaches to solve this problem (here and here).

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of