Find index of 0 to be replaced to get 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.

 

We can efficiently solve this problem in linear time and constant space. The idea is to traverse the given array and maintain index of previous zero encountered. Then for each subsequent zeroes, we can easily find out number of 1’s between current zero and last zero. For each element we check if maximum sequence of continuous 1’s ending at that element (including last zero which is now replaced by 1) exceeds maximum sequence found so far. If yes, we update the maximum sequence to current sequence length and index of optimal zero to index of last zero encountered.

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:

1. By replacing non-zero elements with count of their adjacent consecutive 1’s

2. Using Sliding Window Technique

 

 
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  
newest oldest most voted
Notify of
Phạm Xuân Tích
Guest

Using sliding window, you maybe get O(n^2), you can remove while loop by setting left = prev_zero_index+1 before updating prev_zero_index = i

See more http://ideone.com/z5fsd1

Anton
Guest

I’ve implemented approaches described here and optimised Approach 3 the way you describe, and now Approach 3 is almost indistinguishable from Approach 1.

Anton
Guest

Link to sliding window Approach 3 that looks like Approach 1
https://gist.github.com/antonlogvinenko/584e2c09393a5da9fedc3ac6331bd930

Tony
Guest

This is great problem

arandomguy
Guest

Inside the condition, “If(count>max_count)” count should be initialised to 0.

arandomguy
Guest

My bad. Ignore the previous comment.

anlancan
Guest

this is my solution in javascript code: time complexity O(n + m)

function findIndexOfZero() {
let n = binaryArray1.length;
let indexOfZero = []; // store index of zero in the binary array

for (let i = 0; i < n; i++) {
if (binaryArray1[i] == 0) {
indexOfZero.push(i);
}
}
let max_len = 0;
let previous_index_zero = indexOfZero[0];
let max_index = -1;
for (let j = 1; j max_len) {
max_len = indexOfZero[j] – previous_index_zero;
max_index = indexOfZero[j];
}
previous_index_zero = indexOfZero[j];
}
return max_index;
}