257. Max Consecutive Ones II

Grow a window that contains at most one 0 (the one you'd flip). When a second 0 enters, shrink from the left until only one 0 remains. The largest window seen is the answer.

A window that tolerates one zero

Since you may flip at most one 0, the best run of 1s is the longest subarray containing at most one 0. Slide a window [l, r] and keep a count of zeros inside it.

l = 0; zeros = 0; best = 0
for r in 0..n-1:
    if nums[r] == 0: zeros += 1
    while zeros > 1:                 # too many zeros -> shrink
        if nums[l] == 0: zeros -= 1
        l += 1
    best = max(best, r - l + 1)
return best

Each index enters and leaves the window at most once, so it's a single linear pass.

Worked example

nums = [1, 0, 1, 1, 0].

• r=0: window [1], zeros 0, best 1.
• r=1: window [1,0], zeros 1, best 2.
• r=2: [1,0,1], zeros 1, best 3.
• r=3: [1,0,1,1], zeros 1, best 4.
• r=4: adds a second 0 → shrink until l=2, window [1,1,0], best stays 4.

Answer 4 (flip the first 0 to join the run).

Complexity

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

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int l = 0, zeros = 0, best = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zeros++;
            while (zeros > 1) {
                if (nums[l] == 0) zeros--;
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}