Close

Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s?
For example consider the array
A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the sub-array A[0:4]
This problem can be solved using sliding window algorithm. Take two indexes front and back which defines a window. We keep expanding the window by incrementing the back index as long as the window contains less than or equal to K zeros. That means, at any time, the window contains at most K 0’s. If it exceeds K, we increment the front index to reduce the number of zeros to K. Continue this procedure until the back index reaches the end of the array. We also keep track of the largest window during this process.
This algorithm takes O(n) time.
Here is the C++ code.
Problem Source: SPOJ REPROAD

Leave a Reply

Your email address will not be published. Required fields are marked *