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
This problem can be solved using sliding window algorithm. Take two indexes
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