---
Difficulty: Medium
Source: 160 Days of Problem Solving (BONUS PROBLEMS 🎁)
Tags:
  - Arrays
---

# 🚀 _3. Maximize Number of 1's_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/array-bonus-problems/problem/maximize-number-of-1s0905)

## 💡 **Problem Description:**

Given a binary array `arr[]` (containing only `0s` and `1s`) and an integer `k`, you are allowed to flip at most `k` `0s` to `1s`. Find the maximum number of consecutive `1's` that can be obtained in the array after performing the operation at most `k` times.

### **Examples:**

**Input:**

```
arr[] = [1, 0, 1], k = 1
```

**Output:**

```
3
```

**Explanation:**  
The maximum subarray of consecutive `1's` is of size `3`, obtained by flipping the `0` at index `1`.

**Input:**

```
arr[] = [1, 0, 0, 1, 0, 1, 0, 1], k = 2
```

**Output:**

```
5
```

**Explanation:**  
By flipping the `0's` at indices `4` and `6`, we get the longest subarray of size `5` (from index `3` to `7`).

**Input:**

```
arr[] = [1, 1], k = 2
```

**Output:**

```
2
```

**Explanation:**  
Since the array already contains the maximum consecutive `1's`, no operation is needed. Hence, the answer is `2`.

### **Constraints:**

- $1 \leq \text{arr.size()} \leq 10^5$
- $0 \leq k \leq \text{arr.size()}$
- $0 \leq \text{arr[i]} \leq 1$

## 🎯 **My Approach:**

### Step-by-Step:

1. **Sliding Window Framework:**  
   Use the sliding window technique to maintain a window of valid subarrays with at most `k` zeroes flipped to `1's`.

2. **Two-Pointer Technique:**

   - Initialize two pointers, `left` and `right`, to represent the current window.
   - Traverse the array with the `right` pointer.
   - Track the count of `0's` in the current window using a counter `zeroCount`.

3. **Shrink the Window (if needed):**

   - When the `zeroCount` exceeds `k`, increment the `left` pointer to shrink the window until the condition is satisfied.
   - Adjust the `zeroCount` whenever a `0` is removed from the window.

4. **Track the Maximum Length:**
   - At each step, calculate the size of the current window (`right - left + 1`) and update the maximum length.

## 🕒 **Time and Space Complexity:**

- **Time Complexity:**  
  $O(n)$

  - We traverse the array only once, with the `right` pointer moving from the start to the end of the array.
  - The `left` pointer also moves linearly to adjust the window, but the total number of movements for both pointers is proportional to the size of the array.

- **Auxiliary Space Complexity:**  
  $O(1)$
  - We use only a few variables for tracking indices, counts, and results, irrespective of the size of the input array.

## 📝 **Solution Code**

### Code (C++)

```cpp
class Solution {
public:
    int maxOnes(vector<int>& arr, int k) {
        int maxLen = 0, left = 0, zeroCount = 0;

        for (int right = 0; right < arr.size(); ++right) {
            if (arr[right] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                if (arr[left] == 0) {
                    zeroCount--;
                }
                left++;
            }

            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};
```

### Code (Java)

```java
class Solution {
    public int maxOnes(int[] arr, int k) {
        int maxLen = 0, left = 0, zeroCount = 0;

        for (int right = 0; right < arr.length; right++) {
            if (arr[right] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                if (arr[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}
```

### Code (Python)

```python
class Solution:
    def maxOnes(self, arr, k):
        max_len = 0
        left = 0
        zero_count = 0

        for right in range(len(arr)):
            if arr[right] == 0:
                zero_count += 1

            while zero_count > k:
                if arr[left] == 0:
                    zero_count -= 1
                left += 1

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

        return max_len
```

## 🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>