Find maximum length sequence of continuous ones (Using Sliding Window)

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 have already discussed two approaches to solve this problem (here and here). In this post, another approach is discussed which uses sliding window technique.

 
The idea is to maintain a window containing at-most one zero 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 2 and 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 update the index of 0 to be replaced.

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).

 
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

avatar
  Subscribe  
Notify of