0487.md

487. Max Consecutive Ones II

Level:

Topic:

Similar Problem:

• 340. Longest Substring with At Most K Distinct Characters
• 424. Longest Repeating Character Replacement
• 1004. Max Consecutive Ones III

Question

Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the maximum number of consecutive 1s. After flipping, the maximum number of consecutive 1s is 4.

Intuition

• Slide the window until sees at most 1 zero
• if the number of zerso > 1, shrink the window to the previous zero inclusive

Approach 1: while loop until left pointer meets the first zero in the window Approach 2 (Follow-up): account for the previous zero position and just change left pointer to that position+1

Code

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

public int findMaxConsecutiveOnes(int[] nums) {
    int zero = 0;
    int ans = 0;
    int prevZero = -1;

    // [11111101110111111101111111111111]
    // ^          ^

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

            // check if at most one zero before changing previous zero position
            // if zeros > 1, the new window should be [previous zero position, right]
            if (zero+1 > 1)
                left = prevZero;
            else
                zero++;

            prevZero = right;
        }
        ans = Math.max(ans, right-left);
    }

    return ans;
}