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.


Download   Run Code


Download   Run Code


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

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


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

Notify of