Max Consecutive Ones II

medium array dp sliding window

Problem

Given a binary array nums, return the maximum number of consecutive 1s you can achieve by flipping at most one 0.

Inputnums = [1, 0, 1, 1, 0, 1]

Output4

Flip the first 0 to get [1,1,1,1,0,1]; or the last 0 for [1,0,1,1,1,1]. Best run = 4.

nums (binary, comma-separated)

def find_max_consecutive_ones(nums):
    l = zeros = best = 0
    for r, x in enumerate(nums):
        if x == 0: zeros += 1
        while zeros > 1:
            if nums[l] == 0: zeros -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

function findMaxConsecutiveOnes(nums) {
  let l = 0, zeros = 0, best = 0;
  for (let 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;
}

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;
    }
}

int findMaxConsecutiveOnes(vector<int>& nums) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        if (nums[r] == 0) zeros++;
        while (zeros > 1) {
            if (nums[l] == 0) zeros--;
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Explanation

We may flip a single 0 into a 1, so the longest run of 1s we can build is simply the longest window that contains at most one 0 — that one 0 is the one we'd flip.

We slide a window with a right pointer r, counting zeros inside with zeros. As long as zeros stays at 1 or less, the window is fine and we record its length r - l + 1 in best.

The moment zeros becomes 2, the window has too many 0s, so we move the left pointer l forward, subtracting a zero from the count as it passes, until only one 0 remains inside.

Example: nums = [1,0,1,1,0,1]. The window [1,1,0,1] (indices 2..5 region with one zero) gives length 4. Flipping that single 0 yields four consecutive 1s, which is the answer.

Each index is touched by r once and by l at most once, so it runs in linear time with constant space.

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