Problem Statement

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Examples

Example 1:

Input: nums = [1, 1, 0, 0, 1, 1, 1, 0, 0, 0], k = 2
Output: 7

Explanation: We can flip nums[2] and nums[3] to get [1, 1, 1, 1, 1, 1, 1, 0, 0, 0] and the longest consecutive 1's is 7.

Example 2:

Input: nums = [1, 0, 0, 0, 0, 1, 1, 0, 1, 1], k = 2
Output: 6

Explanation: We can flip nums[4] and nums[7] to 1, which makes [1, 0, 0, 0, 1, 1, 1, 1, 1, 1]. The longest consecutive 1's is 6

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The idea here is to generate all possible substrings of the given array and while doing so, keep a track of all the zeros encountered so far in the substring. If the number of zeros exceeds k then no need to consider that substring, else calculate the length of the current substring and update the maximum length of substring.

Approach: 

1. Iterate the array using for loop which runs from 0 to sizeOfArray - 1, which indicates the starting point of a substring. Now, initialize a variable zero to 0 to keep track number of zeros found so far in the substring.
2. Use another for loop, which basically indicates the ending point of the substring, if the current element is 0, then increase the the variable zero by.
3. If number of 0 in the current substring exceeds k then break out of the inner loop, no need to consider such string. Else, calculate the length of current substring and update the maximum length of substring encountered so far. Finally, return the maximum length of the substring.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the length of the
    longest substring with at most k zeros*/
    int longestOnes(vector<int>& nums, int k) {
        
        // Length of the input array
        int n = nums.size();
        
        //Maximum length of the substring
        int maxLen = 0;
        
        /* Variable to count the number
        of zeros in the current window*/
        int zeros = 0;        
        
        /* Iterate through all possible 
        starting points of the substring*/
        for (int i = 0; i < n; i++) {
            zeros = 0;  
            
            /* Expand the window from starting
            point i to the end of the array*/
            for (int j = i; j < n; j++) {
                if (nums[j] == 0) {
                    
                    /* Increment zeros count 
                    when encountering a zero*/
                    zeros++;  
                }
                
                /* If zeros count is within the 
                allowed limit (k), update maxLen*/
                if (zeros <= k) {
                    
                    // Calculate the length of substring
                    int len = j - i + 1;   
                    maxLen = max(maxLen, len);  
                } else break; 
            }
        }
        
        //Return the maximum length
        return maxLen; 
    }
};

int main() {
    vector<int> input = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
    int k = 2;  
    
    // Create an instance of Solution class
    Solution sol;
    
    int length = sol.longestOnes(input, k);
    
    // Print the result
    cout << "Length of longest substring with at most " << k << " zeros: " << length << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2), where N is the size of the array. As for every element of the array the inner loop runs for N times.
• Space Complexity: O(1) as no extra space is being used.

2️⃣ Better Approach (Sliding Window)

Intuition:

1. Maintaining a Window: We use a sliding window to iterate through the binary array. The window contains at most k zeroes.
2. Expanding the Window: We expand the window to the right as long as the number of zeroes in the window does not exceed k.
3. Shrinking the Window: If the number of zeroes in the window exceeds k, we shrink the window from the left until the number of zeroes in the window is less than or equal to k.
4. Updating the Maximum Length: We keep track of the maximum length of consecutive ones seen so far.

Algorithm:

1. Initialize left and right pointers to 0.
2. Initialize a variable zeroes_count to keep track of the number of zeroes in the current window.
3. Initialize a variable max_ones_count to store the maximum number of consecutive ones seen so far.
4. Iterate through the array using the sliding window approach:
5. Increment right pointer.
6. If nums[right] is 0, increment zeroes_count.
7. If zeroes_count exceeds k, move left pointer until zeroes_count is less than or equal to k.
8. Update max_ones_count with the maximum length of consecutive ones seen so far.
9. Return max_ones_count.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

int longestOnes(vector<int>& nums, int k) {
    int left = 0, right = 0;
    int zeroes_count = 0;
    int max_ones_count = 0;

    while (right < nums.size()) {
        if (nums[right] == 0) {
            zeroes_count++;
        }
        while (zeroes_count > k) {
            if (nums[left] == 0) {
                zeroes_count--;
            }
            left++;
        }
        max_ones_count = max(max_ones_count, right - left + 1);
        right++;
    }

    return max_ones_count;
}

int main() {
    vector<int> nums1 = {1,1,0,0,1,1,1,0,0,0};
    int k1 = 2;
    cout << "Max consecutive ones: " << longestOnes(nums1, k1) << endl;

    vector<int> nums2 = {1,0,0,0,0,1,1,0,1,1};
    int k2 = 2;
    cout << "Max consecutive ones: " << longestOnes(nums2, k2) << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2n), where n is the size of the array.
  • The outer and the inner loop is running for n times.
• Space Complexity:O(1), as no extra space is being used.

3️⃣ Optimal Approach (Sliding Window)

Intuition:

The idea here is to employ the sliding window approach efficiently by avoiding the additional O(N) time complexity incurred when shifting the window entirely in the better solution, to ensure that the total number of zeros does not exceed k. Instead of moving the left pointer (l) to eliminate excess zeros completely, shift the window by one position at a time. This method ensures that the problem can be solved in O(N) time complexity only.

Approach:

1. First, initialize few variables as: l and r as pointers, where l marks the left boundary and r marks the right boundary of the sliding window, zeros to count the number of zeros encountered within the current window, maxLen to store the maximum length of valid substrings found.
2. Use the r pointer to traverse through the array. For each element, check if it is 0. If so, increment the zeros count because we are adding one more zero to the current window.
3. After incrementing zeros, check if zeros exceeds the allowed limit k. If so, adjust the window by moving the l pointer to the right until the window contains at most k zeros (zeros <= k). Decrement the zeros count accordingly when the element pointed by l is 0 and increment l.
4. Whenever zeros is less than or equal to k, calculate the length of the current substring. Update maxLen to store the maximum length encountered so far among all valid substrings. Move r pointer by 1. Finally, return maxLen variable.

Code: