1004.md

1004. Max Consecutive Ones III

Level:

Topic:

Similar Problem:

• 340. Longest Substring with At Most K Distinct Characters
• 487. Max Consecutive Ones II
• 1004. Max Consecutive Ones III

Question

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.

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.

Intuition

1. within the current window, keep count for the flips (the number of zeros)
2. once flips > k, shrink the window until it satisfies flips == k
3. update max if current window size is greater, after step 2, the window is always valid

Code

Time: O(n)
Space: O(1)

public int longestOnes(int[] nums, int k) {
    int flips = 0;
    int ans = 0;

    int left = 0, right = 0;
    while (right < nums.length) {
        if (nums[right++] == 0)
            flips++;

        while (flips > k) {
            if (nums[left++] == 0)
                flips--;
        }
        ans = Math.max(ans, right-left);
    }

    return ans;
}