Sliding Window: Return the maximum consecutive ones after flipping k zeros

Problem Statement:

You are given a binary array and a value K.

You need to return the maximum number of consecutive 1s after flipping at most k zeros.

Example:

Input: arr = [0, 0, 1, 1, 1, 0, 0] k = 2

Output: 5

Explanation: 

You can flip first 2 zeros to 1 and get to the result.

Solution Explanation:

We will use sliding window approach to solve the problem.

Take two pointers right and left and start from index 0.

Expand right window and if nums[right] = 0, then increment zeroCount

If zeroCount > k, then increment left pointer and if nums[left] = 0, then decrement the zeroCount count.

Update the result as maxLen and return the result

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

int solution(vector<int>& nums, int k) 
{
    int n = nums.size();
    int zeroCount = 0;
    int maxLen = 0;
    int left = 0;
    
    for(int right = 0; right < n; right++)
    {
        if(nums[right] == 0) 
        	zeroCount++;
        
        while(zeroCount > k)
        {
            if(nums[left] == 0) 
            	zeroCount--;
            left++;
        }
        
        maxLen = max(maxLen, right - left + 1);
    }
    
    return maxLen;
}


int main()
{

    vector<int> arr = { 1, 1, 0, 1, 1, 1, 1, 0, 0 };
    int k = 2;

    cout << solution(arr, k);
}

Output

8