Intermediate Level
Implement the maxConsecutiveOnesWithKFlips method that returns the longest run of 1 values after flipping at most k zeroes.
The input contains a binary array nums, its length size, and an integer k. You may flip at most k zeroes into ones.
Your task is to return the maximum number of consecutive ones possible after performing at most k flips.
For example, in [1,1,1,0,0,0,1,1,1,1,0] with k = 2, the longest possible run has length 6.
Example 1
Input
nums (int[]) =
[1,1,1,0,0,0,1,1,1,1,0]size (int) =
11k (int) =
2Returns (int)
6Example 2
Input
nums (int[]) =
[0,0,1,1,1,0,0]size (int) =
7k (int) =
0Returns (int)
3Example 3
Input
nums (int[]) =
[0,0,0]size (int) =
3k (int) =
2Returns (int)
2Use a sliding window that keeps at most k zeroes.
Move the right pointer across the array and count zeroes inside the window. If the zero count becomes greater than k, move the left pointer until the window is valid again.
The largest valid window length is the answer.
Pseudocode:
function maxConsecutiveOnesWithKFlips(nums, size, k):
left = 0
zeroCount = 0
best = 0
for right from 0 to size - 1:
if nums[right] == 0:
zeroCount++
while zeroCount > k:
if nums[left] == 0:
zeroCount--
left++
best = maximum(best, right - left + 1)
return bestReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run