# Max Consecutive Ones III

## Problem

Given a binary array `nums` and an integer `k`, return *the maximum number of consecutive* `1`*'s in the array if you can flip at most* `k` `0`'s. ([link](https://leetcode.com/problems/max-consecutive-ones-iii/description/))

**Example 1:**

```plaintext
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
```

**Example 2:**

```plaintext
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
```

**Constraints:**

- `1 <= nums.length <= 10<sup>5</sup>`
- `nums[i]` is either 0 or 1.
- `0 <= k <= nums.length`

## Solution

### Brute force approach

Instead of flipping zeros, find the longest subarray containing **at most** `k` **zeros**. Those zeros can all be flipped to ones. This is the longest-window idea from [pattern 2](https://chetan77.hashnode.dev/2-pointers-sliding-window-templates).

Try every starting index and extend the subarray to the right. Stop when the zero count exceeds `k`, because extending further cannot reduce it.

```java
class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        
        for(int i=0; i<n; i++){
            int zeros = 0;
            for(int j=i; j<n; j++){
                
                if(nums[j] == 0){
                    zeros += 1;
                }

                if(zeros > k){
                    break;
                }

                maxLength = Math.max(maxLength, j-i+1);
            }
        }

        return maxLength;
    }
}
```

**Time:** O(n²) in the worst case. **Extra space:** O(1).

### Better solution

Use a window from `l` to `r` and track its zero count:

1. Add `nums[r]` to the window.
2. While there are more than `k` zeros, remove elements from the left.
3. Once valid, update the maximum length using `r - l + 1`.

```java
class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        
        int l = 0;
        int r = 0;
        int zeros = 0;

        while(r<n){
            if(nums[r] == 0) {
                zeros += 1;
            }

            while(zeros > k){
                if(nums[l] == 0){
                    zeros -= 1;
                }
                l += 1;
            }

            maxLength = Math.max(maxLength, r-l+1);

            r+=1;
        }

        return maxLength;
    }
}
```

**Time:** O(2n) — each pointer moves forward at most `n` times, even with the inner `while` loop. **Extra space:** O(1).

### Optimal Solution

This version moves `l` only once per iteration when the zero count exceeds `k`. The window may still be invalid, so update the answer only when `zeros <= k`.

Each iteration adds one element and removes at most one, so the window length never decreases. This lets us keep searching for a longer valid window without fully shrinking each time.

```java
class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        
        int l = 0;
        int r = 0;
        int zeros = 0;

        while(r<n){
            if(nums[r] == 0) {
                zeros += 1;
            }

            if(zeros > k){
                if(nums[l] == 0){
                    zeros -= 1;
                }
                l += 1;
            }

            if(zeros <= k)
                maxLength = Math.max(maxLength, r-l+1);

            r+=1;
        }

        return maxLength;
    }
}
```

**Time:** O(n). **Extra space:** O(1). Both sliding-window versions have the same time complexity.