3. Maximize Number of 1's.md

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

💡 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++)

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)

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)

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. Let’s make this learning journey more collaborative!

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

---

📍Visitor Count