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++;
}
ans=max(ans, high-low); //update answer
}
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[5]={1, 0, 1, 1, 0};
int k =2;
int n = sizeof(a)/sizeof(a[0]);
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
People are also reading:
Leave a Comment on this Post