How to find max consecutive 1’s with Kth allowed zero flip ?

[Question] In a. Given a binary array nums and an integer k, find the maximum number of consecutive 1‘s in the array & you can flip at most  k 0‘s.
Example: – var arrMix = [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]
var arrCount = 11
var maxZeros = 2
Hence the output will be 8 i.e 1, 1, 0, 1, 0, 1, 1, 1
This Question can solve by simple sliding window approach
In the below code I have declared startWindowIndex & endWindowIndex we starts moving with loop and if we find zero element we increments maxZeros & at certain time if maxZeros became negative we increase startWindowIndex and as we already decremented maxZeros so now we will allow to enter more zeros if any by maxZeros += 1

// TC: O(n)
// SC: O(1)
func maxConsecutiveOfonesWithFlipiingZeros(arr: inout [Int],
                                           arrCount: inout Int,
                                           maxZeros: inout Int) -> Int {
    
    var startWindowIndex = 0
    var endWindowIndex = 0
    
    for currentWindowIndex in 0..<arrCount {
        if arr[currentWindowIndex] == 0 {
            maxZeros -= 1
        }
        if maxZeros<0 {
            startWindowIndex += 1
            if arr[startWindowIndex] == 0 {
                maxZeros += 1
            }
        }
        endWindowIndex = currentWindowIndex
    }
    return endWindowIndex-startWindowIndex// returns the desired window.
}

var arrMix = [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]
var arrCount = 11
var maxZeros = 2
let op = maxConsecutiveOfonesWithFlipiingZeros(arr: &arrMix,
                                               arrCount: &arrCount,
                                               maxZeros: &maxZeros)
print("op", op)// Prints 8

Leave a Comment

Your email address will not be published. Required fields are marked *