Problem

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

Examples

Example 1:

1
2
3
4
5
6

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

Example 2:

1
2
3
4
5
6

Input: nums = [1,0,1,1,0,1]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

Constraints:

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

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?

Solution

Method 1 – Sliding Window with Zero Flip

Intuition

We want the longest sequence of 1s, allowing at most one 0 to be flipped to 1. By using a sliding window, we can efficiently track the window containing at most one 0 and update the maximum length found.

Approach

  1. Initialize two pointers l and r for the window, and a variable zero to count zeros in the window.
  2. Move the right pointer r through the array:
    • If nums[r] is 0, increment zero.
    • If zero exceeds 1, move the left pointer l right until zero is at most 1.
    • Update the answer with the current window size.
  3. Return the maximum window size found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int l = 0, ans = 0, zero = 0;
        for (int r = 0; r < nums.size(); ++r) {
            if (nums[r] == 0) zero++;
            while (zero > 1) {
                if (nums[l++] == 0) zero--;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func findMaxConsecutiveOnes(nums []int) int {
    l, ans, zero := 0, 0, 0
    for r, x := range nums {
        if x == 0 {
            zero++
        }
        for zero > 1 {
            if nums[l] == 0 {
                zero--
            }
            l++
        }
        if r-l+1 > ans {
            ans = r-l+1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int l = 0, ans = 0, zero = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zero++;
            while (zero > 1) {
                if (nums[l++] == 0) zero--;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun findMaxConsecutiveOnes(nums: IntArray): Int {
        var l = 0
        var ans = 0
        var zero = 0
        for (r in nums.indices) {
            if (nums[r] == 0) zero++
            while (zero > 1) {
                if (nums[l++] == 0) zero--
            }
            ans = maxOf(ans, r - l + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        l = ans = zero = 0
        for r, x in enumerate(nums):
            if x == 0:
                zero += 1
            while zero > 1:
                if nums[l] == 0:
                    zero -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn find_max_consecutive_ones(nums: Vec<i32>) -> i32 {
        let (mut l, mut ans, mut zero) = (0, 0, 0);
        for (r, &x) in nums.iter().enumerate() {
            if x == 0 {
                zero += 1;
            }
            while zero > 1 {
                if nums[l] == 0 {
                    zero -= 1;
                }
                l += 1;
            }
            ans = ans.max(r as i32 - l as i32 + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findMaxConsecutiveOnes(nums: number[]): number {
        let l = 0, ans = 0, zero = 0;
        for (let r = 0; r < nums.length; r++) {
            if (nums[r] === 0) zero++;
            while (zero > 1) {
                if (nums[l++] === 0) zero--;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, since we scan the array once.
  • 🧺 Space complexity: O(1), as only a few variables are used.