1s after flipping at most k zeroes.
Problem
Given a binary array nums and an integer k, return the maximum number of consecutive1s that can be obtained by flipping at most k zeroes to 1. The goal is to find the longest contiguous subarray containing at most k zeroes.
Example(s)
Consider the following example(s) to understand the expected input and output.Example 1
Input
nums = [1,1,1,0,0,0,1,1,1,1,0]
k = 2Output
6Example 2
Input
nums = [0,0,1,1,1,0,0]
k = 0Output
3Solution
This solution uses the Sliding Window technique. We maintain a window containing at mostk zeroes. The right pointer expands the window, while the left pointer moves forward whenever the window contains more than k zeroes. For every element, if it is
0, we increase the zero count. If the number of zeroes becomes greater than k, we move left forward until the window becomes valid again. At every valid window, we update the maximum length. Since the window contains at most
k zeroes, all of those zeroes can be flipped to 1s.
class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0;
int zeroes = 0;
int max = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) {
zeroes++;
}
while (zeroes > k) {
if (nums[left] == 0) {
zeroes--;
}
left++;
}
max = Math.max(max, right - left + 1);
}
return max;
}
}Complexity
Each element enters and leaves the sliding window at most once, so the time complexity isO(n), where n is the length of the array. The solution uses only a few variables to maintain the window, so the extra space complexity is
O(1).