Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explored algorithms to Find the longest sequence of consecutive ones when atmost k zeros can be altered to 1. This involve techniques like Sliding Window approach.
| Table of Contents |
|---|
| 1) Problem statement |
| 2) Naive approach |
| 3) Sliding Window approach |
| 4) Conclusion |
1)Problem statement
Given a binary array. Find the longest sequence of consecutive ones when atmost k zeros can be altered to 1.
For example,
Let the binary array be nums=[1,0,1,1,0,0,1,0].
Let k be 2.
Flipping zeros at indices (4,5) or (1,4) will give consecutive sequence of ones containing 5 ones which is the longest possible sequence of ones.
2)Naive approach
It is said that k zeros can be flipped, so instead of flipping the zeros let's search for a sequence containing atmost k zeros.
In this approach considering each index of the array, we find the subarray starting with that index which contains ones and atmost k zeros. At any instance while traversing for the subarray if number of zeros are greater than k the process of finding the subarray for that index is stopped and will proceed for the next index.
The longest of all such subarrays is tracked.
Let's look at dry run of the algorithm.
nums=[1,0,1,1,0,0,1,0]
k=2
Let the length of the maximum subarray containing all 1s with atmost k zeros flipped is res.
Initialize res=0
For index=0
[1,0,1,1,0,0,1,0] currSubArrayLength=5
res=max(res,currSubArrayLength)=max(0,5)=5
For index=1
[1,0,1,1,0,0,1,0] currSubArrayLength=4
res=max(res,currSubArrayLength)=max(5,4)=5
For index=2
[1,0,1,1,0,0,1,0] currSubArrayLength=5
res=max(res,currSubArrayLength)=max(5,5)=5
For index=3
[1,0,1,1,0,0,1,0] currSubArrayLength=4
res=max(res,currSubArrayLength)=max(5,4)=5
For index=4
[1,0,1,1,0,0,1,0] currSubArrayLength=3
res=max(res,currSubArrayLength)=max(5,3)=5
For index=5
[1,0,1,1,0,0,1,0] currSubArrayLength=3
res=max(res,currSubArrayLength)=max(5,3)=5
For index=6
[1,0,1,1,0,0,1,0] currSubArrayLength=2
res=max(res,currSubArrayLength)=max(5,2)=5
For index=7
[1,0,1,1,0,0,1,0] currSubArrayLength=1
res=max(res,currSubArrayLength)=max(5,1)=5
Hence the maximum consecutive ones when 2 zeros can be flipped in the array nums=[1,0,1,1,0,0,1,0] is 5.
Implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
int nums[]={1,0,1,1,0,0,1,0};
int n=sizeof(nums)/sizeof(nums[0]);
int k=2;
int res=0;
int zeros,ones;
for(int i=0;i<n;i++)
{
//intialize the counts to 0
zeros=0,ones=0;
//start from index i
int j=i;
//traverse through the array
for(;j<n;j++)
{
//if 0 is encountered increment zeros count by one
if(nums[j]==0)
zeros++;
//if 1 is encountered increment ones count by one
else
ones++;
//if zeros count is greater than k then
//break the loop(stop considering elements from then)
//because we can have atmost k zeros in the subarray
if(zeros>k)
break;
}
//j-1 is the index at which the subarray ends
//hence (j-1-i+1)=(j-i) gives the length of the subarray
res=max(res,j-i);
}
//print length of the maximum subarray containing all 1s with atmost k zeros flipped
cout<<res<<endl;
return 0;
}
5
The time complexity for the naive approach is O(n2)
Traverse through the array - O(n)
For each index find a subarray which contains all 1s with k 0s flipped - O(n)
Hence, the complexity is O(n2).
The time complexity can be improved using the optimized approach.
Let's look at the sliding window approach.
3)Sliding Window approach
In this approach a window is maintained based on given constraints.
Here, the constraint is to have atmost k zeros in the subarray with rest of the elements as ones.
A window is said to be stable if it contains atmost k zeros otherwise it is unstable.
Hence, whenever the window becomes unstable we slide the window.
There will be two pointers left and right which are bounds of the window, each time the window becomes unstable the left pointer will moved to decrease the size of the window until the window becomes stable.
ALGORITHM
1.Initialize two variables l,r to zero indicating the left and right bounds of the window
2.Increment the size of the window with r
2.1.If a zero is encountered increment the zeros count
2.2.If a one is encountered increment the ones count
2.3.When the window becomes unstable i.e., zeros count becomes more than k decrease the size of the window using l until the window becomes stable
2.3.1.If a zero is encountered decrement the zeros count
2.3.2.If a one is encountered decrement the ones count
2.3.3.Increment l
2.4.Keep track of the maximum subarray
Let's look at dry run of the algorithm.
nums=[1,0,1,1,0,0,1,0]
k=2
Let the length of the maximum subarray containing all 1s with atmost k zeors flipped be res.
Initialize res=0
Let l,r be the left and right bounds of the window respectively.
Initialize l=0,r=0
Let zeros,ones be the zeros and ones count in the window respectively.
Initialize zeros=0,ones=0
Increment the window size using r
r=0
nums[r]=1
ones=ones+1=0+1=1
res=max(res,r-l+1)=max(0,0-0+1)=1
r=1
nums[r]=0
zeros=zeros+1=0+1=1
res=max(res,r-l+1)=max(1,1-0+1)=2
r=2
nums[r]=1
ones=ones+1=1+1=2
res=max(res,r-l+1)=max(2,2-0+1)=3
r=3
nums[r]=1
ones=ones+1=2+1=3
res=max(res,r-l+1)=max(2,2-0+1)=3
r=4
nums[r]=0
zeros=zeros+1=1+1=2
res=max(res,r-l+1)=max(3,4-0+1)=5
r=5
nums[r]=0
zeros=zeros+1=2+1=3
Here, the number of zeros are greater than k hence decrease the window using l and update the counts
l=0 nums[l]=1
ones=ones-1=3-1=2
l=1 nums[l]=0
zeros=zeros-1=3-1=2
l=2
The number of zeros in the current window are atmost k. Hence, stop reducing the window
res=max(res,r-l+1)=max(5,5-2+1)=5
r=6
nums[r]=1
ones=ones+1=2+1=3
res=max(res,r-l+1)=max(5,6-2+1)=5
r=7
nums[r]=0
zeros=zeros+1=1+1=3
Here, the number of zeros are greater than k hence decrease the window using l and update the counts
l=2 nums[l]=1
ones=ones-1=3-1=2
l=3 nums[l]=1
ones=ones-1=2-1=1
l=4 nums[l]=0
zeros=zeros-1=3-1=2
l=5
The number of zeros in the current window are atmost k. Hence, stop reducing the window
res=max(res,r-l+1)=max(5,7-5+1)=5
Hence the maximum consecutive ones when 2 zeros can be flipped in the array nums=[1,0,1,1,0,0,1,0] is 5.
Implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
int nums[]={1,0,1,1,0,0,1,0};
int n=sizeof(nums)/sizeof(nums[0]);
int k=2;
int res=0;
int zeros,ones,l,r;
//intialize the counts to 0
zeros=0,ones=0;
//intially there will be no elements in the window
//hence the l,r will be pointing to the first index
l=0,r=0;
while (r<n)
{
//if 0 is encountered increment zeros count by one
if(nums[r]==0)
zeros++;
//if 1 is encountered increment ones count by one
else
ones++;
//the below while loop gets executed whenever the window becomes
//unstable i.e., zeros count becomes greater than k
//whenever the zeros count becomes greater than k reduce the window until
//the given constraints are fulfilled i.e., zeros count becomes less than or equal to k
//the execution of the loop halts when the window is stable
while(l<r and zeros>k)
{
//if 0 is encountered decrement zeros count by one i.e., remove that 0 from the window
if(nums[l]==0)
zeros--;
//if 1 is encountered decrement ones count by one i.e., remove that 1 from the window
else
ones--;
//decrease the window size by incrementing left bound of the window
l++;
}
//since we are dealing with indices (r-l+1) would give the length of the subarray
//keep track of the maximum subarray
res=max(res,r-l+1);
//increment r irrespective whether the window will be stable or not
//because l takes care of the stability of thw window
r++;
}
//print length of the maximum subarray containing all 1s with atmost k zeros flipped
cout<<res<<endl;
return 0;
}
5
4)Conclusion
The Sliding Window approach takes O(n) time complexity as the array will be traversed twice using the two pointers.
Traverse by left pointer l - O(n)
Traverse by right pointer r - O(n)
Summing up it's O(n+n)= O(2*n)= O(n)
Hence the time complexity is O(n) where n is the size of the given binary array.
