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

Adhoc / Algorithms / Arrays / Competitive programming / Queue / SPOJ