# LeetCode 1004: Max Consecutive Ones III

## Problem Restatement

We are given a binary array `nums` and an integer `k`.

We can flip at most `k` zeros to ones.

We need to return the maximum number of consecutive ones in the array after performing at most `k` flips.

The official constraints state that `1 <= nums.length <= 10^5`, `nums[i]` is either `0` or `1`, and `0 <= k <= nums.length`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary array `nums` and integer `k` |
| Output | Length of longest subarray of all ones after at most `k` flips |
| Flip | Change `0` to `1` |

Function shape:

```python
def longestOnes(nums: list[int], k: int) -> int:
    ...
```

## Examples

Example 1:

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

Flip two zeros at indices 9 and 10:

```python
[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1]
```

But a better choice flips zeros at indices 3 and 4 or 9 and 10 to get:

The optimal window is from index `3` to `10`, flipping two zeros.

Answer:

```python
6
```

Example 2:

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

Flip zeros at indices 4, 5, and 9 to get a window of 10 ones.

Answer:

```python
10
```

## Key Insight

We want the longest window `[left, right]` that contains at most `k` zeros.

Use a sliding window:

- Expand the right end.
- If the window has more than `k` zeros, shrink the left end.
- Track the maximum window size.

## Algorithm

1. Use two pointers `left = 0` and `right = 0`.
2. Track `zeros`, the count of zeros in the current window.
3. For each `right`:
   - If `nums[right] == 0`, increment `zeros`.
   - While `zeros > k`, if `nums[left] == 0`, decrement `zeros`. Move `left` right.
   - Update the maximum length as `right - left + 1`.
4. Return the maximum length.

## Correctness

At every step, the window `[left, right]` contains exactly `zeros` zeros.

When `zeros > k`, we shrink the left side until `zeros <= k` again.

Since both pointers only move right, each element is added and removed at most once.

The maximum window size found over all positions is the answer, because every valid window is considered.

## Edge Cases

- Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
- Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
- When the target is absent, the loop should still terminate and return the problem-specific failure value.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each pointer moves left to right once |
| Space | `O(1)` | Only a few variables |

## Common Pitfalls

- Do not mix inclusive and half-open bounds inside the same loop.
- Make sure each branch strictly reduces the search interval.

## Implementation

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

        for right in range(len(nums)):
            if nums[right] == 0:
                zeros += 1

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

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

        return best
```

## Code Explanation

We expand the window to the right:

```python
for right in range(len(nums)):
    if nums[right] == 0:
        zeros += 1
```

When the zero count exceeds `k`, shrink from the left:

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

After adjustment, the window is valid. Update the best:

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

## Testing

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

    assert s.longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2) == 6
    assert s.longestOnes([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3) == 10
    assert s.longestOnes([1, 1, 1], 0) == 3
    assert s.longestOnes([0, 0, 0], 0) == 0
    assert s.longestOnes([0, 0, 0], 3) == 3

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `k=2` example | `6` | Flip two zeros in optimal window |
| `k=3` example | `10` | Flip three zeros in optimal window |
| All ones | `3` | No flips needed |
| All zeros, `k=0` | `0` | Cannot flip any |
| All zeros, `k=3` | `3` | Flip all three |