Solution
The problem is similar to longest subarray sum so the first approach which comes into mind is a two pointer approach which is indeed correct. We will two points, i and j. We will keep incrementing i as we traverse through the array. If we come across a 0, we will decrement K. If K==-1, that means we have flipped one extra zero. We will then start incrementing j until we encounted another 0 (so that we do not flip this and K becomes 0). Think of j as an anchor.
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=2
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=-1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=-1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=-1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=-1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=-1
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
i
[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
j
K=0
Code implementation:
int longestOnes(vector<int>& A, int K) {
int res=0, i, j;
for (i=0, j=0; i<A.size(); i++) {
if (A[i] == 0) {
K--;
}
if (K==-1) {
res = max(res, i-j);
while (j<i && A[j]==1) j++;
j++;
K++;
}
}
res = max(res, i-j);
return res;
}
Time complexity: O(n) Space complexity: O(1)