# Find Maximum Sequence of Continuous 1s Formed by Replacing at-most ‘k’ 0s by 1s

Posted in  Vinay Khatri
Last updated on December 4, 2023

## Problem

Given a binary array and an integer ``` k ``` , return the maximum number of consecutive 1 's in the array if you can flip at most k 0s .

## Brute Force Approach

You may travel ahead for each index and see how far you can get by substituting at max k 0's. This technique will work. However, it is inefficient because the time complexity is O(N2). Let's take a different strategy.

## Efficient Approach

The sliding window technique is used in the efficient approach. To begin, check how far you can get by using all k. The low index of the window will now be 0, and the high index will be some index larger than or equal to 0 (>=0). If you see 1 at index high , always increase your high . If the element with the index high is 0, then use the approach listed below. Whenever you encounter 0 at a high index, you always have to increment low but take care of these two cases:

Case 1

If the ``` low ``` index has 0 at its place, you can increment the index ``` high ``` as the element at the index ``` high ``` is replaced with 1 since the element at ``` low ``` index is ``` 0 ``` as ``` k ``` will increase once we move ``` low ``` forward.

Case 2

If index ``` low ``` has 1, then we can’t increment ``` high ``` because ``` k ``` is still ``` 0 ``` .

### C++ Programming

``````#include<bits/stdc++.h>
using namespace std;
int longestOnes(vector<int>& a, int k) {
int n=a.size();
int i=0;
int ans = 0;
while(k && i<n){    //utilize all k
if(a[i]==0) k--;
i++;
}
ans=i;
int low=0, high=i;   //initial window
while(high<n){
if(a[high]==1) high++;   //if element is 1, hust increment
else{
if(a[low]==0)
{
high++;
}
low++;
}
}
return ans;
}
int main(){
vector<int>v{1, 0, 1, 1, 0};
int k =1;
cout<<longestOnes(v, k);
}``````

Output

``4``

### C Programming

``````#include<stdio.h>
int longestOnes(int* a, int n, int K){
if (n == 0) return 0;

int max = 0;
int zeroCount = 0;

int low = 0;    //window indices
int high = 0;

while (high < n) {
if (zeroCount <= K) {
if (a[high] == 0) zeroCount++;  //if element at index high is 0
} else {
if (a[low] == 0) zeroCount--;   //if element at index low is 0
low++;
}
if (zeroCount <= K) {
int ones = (high + 1) - low;
max = ones > max ? ones : max;
high++;
}
}

return max;
}
void main(){
int a={1, 0, 1, 1, 0};
int k =2;
int n = sizeof(a)/sizeof(a);
printf("%d", longestOnes(a, n, k));
}``````

Output

``5``

### Python Programming

``````def longestOnes(nums,k):
low = 0     #initialize indices
high = 0
countZeros = 0   #number of 0s converted to 1
l = len(nums)
ans = 0
while high < l:
if nums[high] == 1:
high += 1
else:
countZeros += 1
while countZeros > k:
if nums[low] == 0:
countZeros -= 1
low += 1
high += 1
ans = max(ans, high - low)    #update answer
ans = max(ans, high - low)
return ans
l  = [1, 0, 1, 0, 1]
k = 2
print(longestOnes(l, k))``````

Output

``5``