Description

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.

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.

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.

Constraints:

  • 1 <= nums.length <= 10^5
  • nums[i] is either 0 or 1.
  • 0 <= k <= nums.length

Solution

In this case, it’s mentioned that we can flip k numbers to achieve maximum subarray of 1’s. In a sense, we can say that we are looking for longest subarray which contains at most k 0’s. Now, this problem becomes similar to sliding window problem where we can have two pointers, left and right. right pointer moves forward keeping track of largest subarray. In this case, subarray becomes invalid when numbers of 0’s become more than k. In this at every point, we can find the current number of 1’s using (right - left) + 1. We also keep track of zero count, because we are allowed to flip k zeroes.

 1left = right = zeroCount = 0
 2maxCount = minimum value
 3while (right less than nums.length)
 4    if nums[right] equal to 0
 5        zeroCount++
 6    while zeroCount > k
 7        if nums[left] == 0
 8            zeroCount--
 9        left++
10    maxCount = max of maxCount and (right - left) + 1
11    right++
12return maxCount

Alternatively, we can use for loop for right pointer.

 1left = zeroCount = 0
 2maxCount = minimum value possible
 3for (right = 0; right less than nums.length; right++)
 4    if nums[right] is 0
 5        zeroCount++
 6    while zeroCount > k
 7        if nums[left] == 0
 8            zeroCount--
 9        left++
10    maxCount = max of maxCount and (right - left + 1)
11return maxCount

This algorithm implemention looks like this in Java.

 1class Solution {
 2    public int longestOnes(int[] nums, int k) {
 3        int left = 0, zeroCount = 0;
 4        int maxCount = Integer.MIN_VALUE;
 5        for (int right = 0; right < nums.length; right++) {
 6            if (nums[right] == 0) {
 7                zeroCount++;
 8            }
 9            while (zeroCount > k) {
10                if (nums[left] == 0)
11                    zeroCount--;
12                left++;
13            }
14            maxCount = Math.max(maxCount, right - left + 1);
15        }
16        return maxCount;
17    }
18}