Find Maximum Sequence of Continuous 1s Formed by Replacing at-most ‘k’ 0s by 1s

Posted in

Find Maximum Sequence of Continuous 1s Formed by Replacing at-most ‘k’ 0s by 1s
vinaykhatri

Vinay Khatri
Last updated on April 14, 2024

    Problem

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

    Brute Force Approach

    You may travel ahead for each index and see how far you can get by substituting at max k 0's. This technique will work. However, it is inefficient because the time complexity is O(N2). Let's take a different strategy.

    Efficient Approach

    The sliding window technique is used in the efficient approach. To begin, check how far you can get by using all k. The low index of the window will now be 0, and the high index will be some index larger than or equal to 0 (>=0). If you see 1 at index high , always increase your high . If the element with the index high is 0, then use the approach listed below. Whenever you encounter 0 at a high index, you always have to increment low but take care of these two cases:

    Case 1

    If the low index has 0 at its place, you can increment the index high as the element at the index high is replaced with 1 since the element at low index is 0 as k will increase once we move low forward.

    Case 2

    If index low has 1, then we can’t increment high because k is still 0 .

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    int longestOnes(vector<int>& a, int k) {
        int n=a.size();
        int i=0;
                int ans = 0;
        while(k && i<n){    //utilize all k
        if(a[i]==0) k--;
        i++;
        }
        ans=i;
        int low=0, high=i;   //initial window
        while(high<n){
            if(a[high]==1) high++;   //if element is 1, hust increment
            else{ 
                if(a[low]==0)   
                {
                high++;
                }
                low++;
            }
            ans=max(ans, high-low);   //update answer
        }
            return ans;
        }
    int main(){
        vector<int>v{1, 0, 1, 1, 0};
        int k =1;
        cout<<longestOnes(v, k);
    }

    Output

    4

    C Programming

    #include<stdio.h>
    int longestOnes(int* a, int n, int K){
        if (n == 0) return 0;
        
        int max = 0;
        int zeroCount = 0;
        
        int low = 0;    //window indices
        int high = 0;
        
        while (high < n) {
            if (zeroCount <= K) {
                if (a[high] == 0) zeroCount++;  //if element at index high is 0
            } else {
                if (a[low] == 0) zeroCount--;   //if element at index low is 0
                low++;
            }
            if (zeroCount <= K) {
                int ones = (high + 1) - low;
                max = ones > max ? ones : max;
                high++;
            }
        }
        
        return max;
    }
    void main(){
        int a[5]={1, 0, 1, 1, 0};
        int k =2;
        int n = sizeof(a)/sizeof(a[0]);
        printf("%d", longestOnes(a, n, k));
    }

    Output

    5

    Python Programming

    def longestOnes(nums,k):
            low = 0     #initialize indices
            high = 0
            countZeros = 0   #number of 0s converted to 1
            l = len(nums)
            ans = 0
            while high < l:
                if nums[high] == 1:
                    high += 1
                else:
                    countZeros += 1                
                    while countZeros > k:
                        if nums[low] == 0:
                            countZeros -= 1
                        low += 1
                    high += 1
                ans = max(ans, high - low)    #update answer
            ans = max(ans, high - low)
            return ans
    l  = [1, 0, 1, 0, 1]
    k = 2
    print(longestOnes(l, k))

    Output

    5

    People are also reading:

    Leave a Comment on this Post

    0 Comments