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.
Test Cases
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Solution
class Solution {
public int longestOnes(int[] nums, int k) {
int windowLeft = 0, windowRight = 0;
int bestWindow = 0, bestLeft = 0;
int n = nums.length, zeroCount = 0;
while(windowRight < n) {
if (zeroCount <= k) {
if (nums[windowRight] == 0) zeroCount++;
windowRight++;
}
if (zeroCount > k) {
if (nums[windowLeft] == 0) zeroCount--;
windowLeft++;
}
if (windowRight-windowLeft > bestWindow && zeroCount <= k) {
bestWindow = windowRight-windowLeft;
bestLeft = windowLeft;
}
}
return bestWindow;
}
}