Given an Boolean array, find the maximum sequence of continuous 1’s that can be formed by replacing at-most k zeroes by ones.

{ 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0 }

For k = 0,

The length of longest sequence is 4 (from index 6 to 9)

For k = 1,

The length of longest sequence is 7 (from index 3 to 9)

For k = 2,

The length of longest sequence is 10 (from index 0 to 9)

For k = 3,

The length of longest sequence is 11 (from index 0 to 10)

We can solve this problem by using sliding window technique. The idea is to maintain a window containing at-most k zeroes 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 more than k. Then 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 set the maximum window size to current window size.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <bits/stdc++.h> using namespace std; // Function to find the maximum sequence of continuous 1's by replacing // atmost k 0's by 1 using sliding window technique void longestSeq(bool arr[], int n, int k) { int left = 0; // left represents current window's starting index int count = 0; // stores number of zeros in current window int window = 0; // stores maximum number of continuous 1's found // so far (including k zeroes) int leftIndex = 0; // store left index of maximum window found so far // maintain a window [left..right] containing at-most k zeroes for (int right = 0; right < n; right++) { // if current element is 0, increase count of zeros in the // current window by 1 if (arr[right] == 0) count++; // window becomes unstable if number of zeros in it becomes // more than k while (count > k) { // if we have found zero, decrement number of zeros in the // current window by 1 if (arr[left] == 0) count--; // remove elements from the window's left side till window // becomes stable again left++; } // when we reach here, the window [left..right] contains at-most // k zeroes and we update max window size and leftmost index // of the window if (right - left + 1 > window) { window = right - left + 1; leftIndex = left; } } // print maximum sequence of continuous 1's cout << "The longest sequence has length " << window << " from index " << leftIndex << " to " << (leftIndex + window - 1); } // main function int main() { bool arr[] = { 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0 }; int k = 2; int n = sizeof(arr) / sizeof(arr[0]); longestSeq(arr, n, k); return 0; } |

`Output:`

The longest sequence has length 10 from index 0 to 9

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Exercise:** Extend the solution to print the index of all zeroes replaced.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply