Sliding Window: Maximum consecutive ones by flipping K bits

Problem Statement:

You are given a binary array and integer k.

You need to return the maximum consecutive 1s in the array by flip at most k 0’s.

Example:

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

Output: 5

Explanation: [1, 1, 1, 1, 1]

Solution Explanation:

We will solve the problem with the help of sliding window approach.

Slide the window from left to right, if we encounter a 0, then increment the zero counter and if the zero count is greater than k, shrink the left window till the zero count is less than k.

While returning to the loop again, calculate the max length and continue.

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 left = 0;
    int result = 0;
    int zeroCount = 0;

    for (int right = 0; right < nums.size(); right++) 
    {
        if (nums[right] == 0) 
        {
            zeroCount++;
        }

        while (zeroCount > k) 
        {
            if (nums[left] == 0) {
                zeroCount--;
            }
            left++;
        }
        result = max(result, right - left + 1);
    }

    return result;
}

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

    cout << solution(arr, k);
}

Output

5