# LeetCode 487: Max Consecutive Ones II

## Problem Restatement

We are given a binary array `nums`.

We may flip at most one `0` into `1`.

Return the maximum number of consecutive `1`s we can get after doing this optimally. The array length is at most `10^5`, and every element is either `0` or `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A binary integer array `nums` |
| Output | Maximum consecutive `1`s after flipping at most one `0` |
| Allowed operation | Flip zero or one `0` into `1` |
| Constraint | `1 <= nums.length <= 10^5` |

Function shape:

```python
def findMaxConsecutiveOnes(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 0, 1, 1, 0]
```

If we flip the first `0`:

```text
[1, 1, 1, 1, 0]
```

The longest run has length `4`.

If we flip the second `0`:

```text
[1, 0, 1, 1, 1]
```

The longest run has length `3`.

Answer:

```python
4
```

Example 2:

```python
nums = [1, 0, 1, 1, 0, 1]
```

Flipping either zero can give a run of length `4`.

Answer:

```python
4
```

## First Thought: Try Every Zero

One direct idea is to try flipping each `0`.

For every zero index:

1. Pretend this zero becomes `1`.
2. Count the longest run of `1`s.
3. Keep the best answer.

This works, but it can scan the array again for each zero.

In the worst case, there may be `O(n)` zeroes, and each check costs `O(n)`.

So the total cost can become:

```text
O(n^2)
```

That is too slow for `n = 100000`.

## Key Insight

After flipping at most one `0`, any valid consecutive block may contain at most one zero.

So the problem becomes:

Find the longest contiguous subarray containing at most one `0`.

This is a sliding window problem.

We keep a window:

```text
nums[left:right + 1]
```

The window is valid while it contains at most one zero.

If adding `nums[right]` makes the window contain two zeroes, we move `left` rightward until the window becomes valid again.

## Algorithm

Initialize:

```python
left = 0
zeros = 0
best = 0
```

Scan `right` from left to right.

For each `nums[right]`:

1. If it is `0`, increment `zeros`.
2. While `zeros > 1`, move `left` forward.
3. If the removed value was `0`, decrement `zeros`.
4. Update `best` with the current window length.

The window length is:

```python
right - left + 1
```

## Correctness

The algorithm maintains a window with at most one zero.

When `nums[right]` is added, the zero count is updated. If the window has more than one zero, moving `left` forward removes elements from the window until at most one zero remains.

Therefore, after the shrinking step, the current window is always a valid subarray that can be turned into all `1`s by flipping at most one zero.

For each right endpoint, the algorithm keeps the leftmost possible `left` that makes the window valid. That gives the longest valid window ending at `right`.

Since every possible answer has some right endpoint, and the algorithm checks the best valid window for every right endpoint, the maximum recorded length is the required answer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves from left to right at most once |
| Space | `O(1)` | Only counters and pointers are used |

## Implementation

```python
class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        left = 0
        zeros = 0
        best = 0

        for right, num in enumerate(nums):
            if num == 0:
                zeros += 1

            while zeros > 1:
                if nums[left] == 0:
                    zeros -= 1
                left += 1

            best = max(best, right - left + 1)

        return best
```

## Code Explanation

The left boundary starts at the beginning:

```python
left = 0
```

The window initially has no zeroes:

```python
zeros = 0
```

As we expand the right side:

```python
for right, num in enumerate(nums):
```

we count zeroes:

```python
if num == 0:
    zeros += 1
```

If the window has two zeroes, it can no longer be fixed with one flip:

```python
while zeros > 1:
```

So we move the left boundary. If we remove a zero, the zero count decreases:

```python
if nums[left] == 0:
    zeros -= 1
left += 1
```

Now the window is valid again, so we update the answer:

```python
best = max(best, right - left + 1)
```

## Stream-Friendly Implementation

The follow-up asks what happens if numbers arrive one by one and we cannot store the whole array.

For at most one flipped zero, we only need the position of the previous zero.

```python
class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        left = 0
        last_zero = -1
        best = 0

        for right, num in enumerate(nums):
            if num == 0:
                left = last_zero + 1
                last_zero = right

            best = max(best, right - left + 1)

        return best
```

When we see a new zero, the previous zero can no longer stay in the same valid window. So the next valid window must start after the previous zero.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findMaxConsecutiveOnes([1, 0, 1, 1, 0]) == 4
    assert s.findMaxConsecutiveOnes([1, 0, 1, 1, 0, 1]) == 4
    assert s.findMaxConsecutiveOnes([1, 1, 1]) == 3
    assert s.findMaxConsecutiveOnes([0, 0, 0]) == 1
    assert s.findMaxConsecutiveOnes([0]) == 1
    assert s.findMaxConsecutiveOnes([1]) == 1
    assert s.findMaxConsecutiveOnes([1, 1, 0, 1, 1, 1]) == 6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 0, 1, 1, 0]` | Main example |
| `[1, 0, 1, 1, 0, 1]` | Two possible flips give same best |
| `[1, 1, 1]` | No zero needs flipping |
| `[0, 0, 0]` | Can flip only one zero |
| `[0]` | Single zero becomes one |
| `[1]` | Single one remains one |
| `[1, 1, 0, 1, 1, 1]` | One zero connects two runs |