#include<bits/stdc++.h>
using namespace std;
int ans(int n,vector&arr,int k){
if(n==0){
return 0;
}
int l = 0;
int count_0 = 0;
int maximum = 0;
for(int i=0;i<n;i++){
if(arr[i]==0){
count_0++;
}
while(count_0>k){
if(arr[l]==0){
count_0--;
l++;
}
}
maximum = max(maximum,i-l+1);
}
return maximum;
}
int main() {
int n;
cin>>n;
int k;
cin>>k;
vectorarr;
for(int i=0;i<n;i++){
int x;
cin>>x;
arr.push_back(x);
}
cout << ans(n,arr,k) << endl;
}
Hi @Mohitpandey29
You are getting TLE because you are approaching this question with time complexity greater then 0(n).
An Efficient Solution can solve the problem in O(n) time and O(1) space. The idea is to use Sliding Window for the given array. The solution is taken from here. Let us use a window covering from index wL to index wR. Let the number of zeros inside the window be zeroCount. We maintain the window with at most m zeros inside.
The main steps are:
While zeroCount is no more than m: expand the window to the right (wR++) and update the count zeroCount.
While zeroCount exceeds m, shrink the window from left (wL++), update zeroCount;
Update the widest window along the way. The positions of output zeros are inside the best window.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.