# Max Consecutive Ones III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/max-consecutive-ones-iii)
Canonical: https://scaleengineer.com/dsa/problems/max-consecutive-ones-iii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [SAP](https://scaleengineer.com/companies/sap), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [tcs](https://scaleengineer.com/companies/tcs), [Snap](https://scaleengineer.com/companies/snap), [Sigmoid](https://scaleengineer.com/companies/sigmoid), [Roku](https://scaleengineer.com/companies/roku)
---
## 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.

**Example 1:**

**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:**

**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 <= 105`
* `nums[i]` is either `0` or `1`.
* `0 <= k <= nums.length`

# Approaches
## Brute Force Approach
This approach involves checking every possible contiguous subarray within the given array. For each subarray, we count the number of zeros. If the count is within the allowed limit `k`, we consider its length as a potential answer and update our maximum length found so far.
**Time:** O(N^2), where N is the number of elements in `nums`. The two nested loops lead to a quadratic runtime, as in the worst case, we might check all N*(N+1)/2 subarrays. · **Space:** O(1), as we only use a few variables to store counts and indices, requiring constant extra space.
**Pros:** Simple to understand and implement.; Directly translates the problem statement into a straightforward solution.
**Cons:** Highly inefficient for large input sizes due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
We use two nested loops to define the start and end of each subarray. The outer loop iterates through all possible start indices `i`, and the inner loop iterates through all possible end indices `j` starting from `i`.

For each subarray `nums[i...j]`, we maintain a count of zeros. If the number of zeros in the current subarray is less than or equal to `k`, it's a valid subarray. We calculate its length (`j - i + 1`) and update the maximum length if this subarray is longer than any valid one found previously.

If the number of zeros exceeds `k`, we can stop extending the current subarray (by breaking the inner loop) because any longer subarray starting at `i` will also have more than `k` zeros. This process is repeated for all possible starting positions `i`.

```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 zeroCount = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == 0) {
                    zeroCount++;
                }
                if (zeroCount <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                } else {
                    // Optimization: if zero count exceeds k, no need to extend this subarray
                    break; 
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize a variable `maxLength` to 0 to store the length of the longest valid subarray found.
- Use a nested loop structure. The outer loop with index `i` will determine the starting point of a subarray.
- The inner loop with index `j` will determine the ending point of the subarray, starting from `i`.
- For each subarray defined by `[i, j]`, maintain a count of zeros, `zeroCount`.
- If `nums[j]` is 0, increment `zeroCount`.
- If `zeroCount` is less than or equal to `k`, the current subarray is valid. Calculate its length `j - i + 1` and update `maxLength = max(maxLength, j - i + 1)`.
- If `zeroCount` exceeds `k`, the subarray is invalid. Since any further extension of this subarray (by increasing `j`) will also be invalid, we can break the inner loop as an optimization.
- After checking all possible starting points `i`, return `maxLength`.

## Optimal Sliding Window Approach
This is a much more efficient approach that solves the problem in linear time. The core idea is to maintain a "window" (a subarray) that has at most `k` zeros. We expand this window by moving its right end and shrink it from the left end whenever the condition (at most `k` zeros) is violated.
**Time:** O(N), where N is the number of elements in `nums`. Each pointer, `left` and `right`, traverses the array at most once, resulting in a single pass over the data. · **Space:** O(1), as we only use a constant amount of extra space for pointers and a counter, regardless of the input size.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large datasets.; It is the optimal solution for this problem.
**Cons:** Can be slightly less intuitive to come up with compared to the brute-force approach, especially for those unfamiliar with the sliding window pattern.
### Explanation
The problem asks for the longest subarray with at most `k` zeros. This structure is a perfect fit for the sliding window technique. We use two pointers, `left` and `right`, to define the current window `[left, right]`.

We iterate through the array with the `right` pointer to expand the window. As we expand, we keep track of the number of zeros inside the current window.

If the count of zeros exceeds `k`, the window is no longer valid. To make it valid again, we must shrink it from the left. We move the `left` pointer to the right, and if the element at the old `left` position was a zero, we decrement our zero count. We continue shrinking until the window is valid again (i.e., `zeroCount <= k`).

At each step, after potentially shrinking, the window `[left, right]` is the longest valid window ending at `right`. We update our overall maximum length with the current window's size (`right - left + 1`). By the time the `right` pointer has traversed the entire array, we will have found the maximum possible length.

```java
class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int zeroCount = 0;
        int maxLength = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            // Shrink the window if it's invalid (too many zeros)
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            // The window [left, right] is now valid.
            // Update the max length.
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize two pointers, `left = 0` and `right = 0`, to represent the boundaries of the sliding window.
- Initialize `zeroCount = 0` to count zeros within the window and `maxLength = 0` to store the result.
- Iterate through the array with the `right` pointer from `0` to `nums.length - 1` to expand the window.
- If `nums[right]` is a 0, increment `zeroCount`.
- After expanding, check if the window is valid. If `zeroCount > k`, the window contains too many zeros. Shrink the window from the left by incrementing the `left` pointer until the window is valid again.
- While shrinking, if the element at `nums[left]` was a 0, decrement `zeroCount`.
- After each expansion and potential shrinking, the window `[left, right]` is valid. Calculate its length `right - left + 1` and update `maxLength = max(maxLength, right - left + 1)`.
- After the `right` pointer has traversed the entire array, return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestOnes(int[] nums, int k) {
    int l = 0, r = 0;
    while (r < nums.length) {
      if (nums[r++] == 0) {
        --k;
      }
      if (k < 0 && nums[l++] == 0) {
        ++k;
      }
    }
    return r - l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestOnes(vector<int> &nums, int k) {
    int l = 0, r = 0;
    while (r < nums.size()) {
      if (nums[r++] == 0)
        --k;
      if (k < 0 && nums[l++] == 0)
        ++k;
    }
    return r - l;
  }
};

```

### Python

```python
class Solution:
    # max-check every for iteration return res ############## class Solution : def longestOnes ( self , nums : List [ int ], k : int ) -> int : l = r = - 1 while r < len ( nums ) - 1 : r += 1 if nums [ r ] == 0 : k -= 1 if k < 0 : l += 1 if nums [ l ] == 0 : k += 1 return r - l
    def longestOnes(self, nums: List[int], k: int) -> int: res, zero, left = 0, 0, 0 for right in range(len(nums)): if nums[right] == 0: zero += 1 while zero > k: if nums[left] == 0: zero -= 1 left += 1 res = max(res, right - left + 1) return res class Solution_followup: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: res, left, k = 0, 0, 1 q = deque() for right in range(len(nums)): if nums[right] == 0: q . append(right) if len(q) > k: left = q . popleft() + 1 res = max(res, right - left + 1)

```