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 arrayA = [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
Adhoc / Algorithms / Arrays / Competitive programming / Queue / SPOJ