[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