Find the maximum sequence of continuous 1’s that can be formed by replacing at-most k zeroes by ones

Given an Boolean array, find the maximum sequence of continuous 1’s that can be formed by replacing at-most k zeroes by ones.

 

For example, consider below binary array

{ 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0 }
 

For k = 0,
The length of longest sequence is 4 (from index 6 to 9)

For k = 1,
The length of longest sequence is 7 (from index 3 to 9)

For k = 2,
The length of longest sequence is 10 (from index 0 to 9)

For k = 3,
The length of longest sequence is 11 (from index 0 to 10)

 


 

We can solve this problem by using sliding window technique. The idea is to maintain a window containing at-most k zeroes at any point. We add elements to the window from right until it becomes unstable. The window becomes unstable if number of zeros in it becomes more than k. Then we remove elements from its left side till it becomes stable again (by removing leftmost zero). If the window is stable and current window length is more than maximum window found so far, we set the maximum window size to current window size.

 
C++ implementation –
 

Download   Run Code

Output:

The longest sequence has length 10 from index 0 to 9

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

Exercise:
Extend the solution to print the index of all zeroes replaced.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz