Maximum Consecutive Ones After Flipping Zeroes in C++
Introduction to Maximum Consecutive Ones After Flipping Zeroes
In many coding interviews and competitive programming problems, you often come across array manipulation tasks. One such interesting problem is “Maximum Consecutive Ones After Flipping Zeroes.”
The goal of this problem is simple:
You are given an array of binary elements (only 0s and 1s). You can flip at most k zeroes to ones. Your task is to find the length of the longest contiguous subarray containing only ones after at most k flips.
Problem Definition - Maximum Consecutive Ones After Flipping Zeroes
Given a binary array and an integer k, find the maximum number of consecutive 1’s that can be achieved by flipping at most k zeroes to ones.
Example 1
Input: arr[] = {1, 0, 1, 1, 0}, k = 1
Output: 4
Explanation: You can flip one zero at index 1 or 4 to get: {1, 1, 1, 1, 0} or {1, 0, 1, 1, 1}. Both will give 4 consecutive 1’s.
Input: arr[] = {0, 0, 1, 1, 0, 1, 1, 0, 1}, k = 2
Output: 7
Explanation: Flip two zeroes at positions 0 and 1 → {1, 1, 1, 1, 0, 1, 1, 0, 1} → maximum 7 consecutive ones.
Output: 5
Explanation: Flip one zero at index 6 → {1, 1, 1, 0, 1, 1, 1, 0} → maximum 5 consecutive ones.
Method for Solving Maximum Consecutive Ones After Flipping Zeroes
List of Methods to solve Consecutive Ones after flipping zeroes:
- Method 1: Naive Approach
- Method 2: Using Sliding Window Technique
Method 1: Naive Approach
In this approach, we explore all possible subarrays and count how many zeroes we flip in each subarray. If the number of flipped zeroes is ≤ k, we update the maximum length.
Algorithm:
(Exploring All Subarrays — O(n²) Time and O(1) Space)
- Initialize maxLen = 0 to store the maximum length of valid subarray.
- Loop through the array with start pointer from index 0 to n-1:
- Initialize zeroCount = 0 for each new subarray starting at start.
- Loop through the array with end pointer from start to n-1:
- If arr[end] == 0, increment zeroCount.
- If zeroCount > k, break the inner loop (invalid subarray).
- Else, update maxLen = max(maxLen, end – start + 1).
3. After both loops, maxLen holds the result.
4. Return maxLen.
Time Complexity: O(n^2)
Space Complexity: O(1)
Code:
#include<iostream>
#include<vector>
using namespace std;
int maxConsecutiveOnesNaive(vector& arr, int k) {
int n = arr.size();
int maxLen = 0;
for (int start = 0; start < n; ++start) {
int zeroCount = 0;
for (int end = start; end < n; ++end) { if (arr[end] == 0) zeroCount++; if (zeroCount > k)
break;
maxLen = max(maxLen, end - start + 1);
}
}
return maxLen;
}
int main() {
vector arr = {1, 0, 1, 1, 0};
int k = 1;
cout << "Maximum Consecutive Ones (Naive): "
<< maxConsecutiveOnesNaive(arr, k) << endl;
return 0;
}
Output:
Maximum Consecutive Ones (Naive): 4
Explanation:
- The code checks all possible subarrays.
- For each subarray, it counts how many zeroes are flipped.
- If flips ≤ k, it updates the result.
- Time Complexity: O(n²), because we use two nested loops.
- Space Complexity: O(1), no extra space used.
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
More Methods
Method 2: Using Sliding Window Technique
This is the optimal approach.
We maintain a window and keep track of how many zeroes are inside it:
- Expand the window by moving the right pointer.
- If the number of zeroes exceeds k, move the left pointer to shrink the window.
- Keep track of the maximum window size.
Algorithm:
- Initialize pointers: left = 0, right = 0.
- Initialize zeroCount = 0 and maxLen = 0.
- While right is less than size of array:
- If arr[right] == 0, increment zeroCount.
- If zeroCount > k:
- While zeroCount > k:
- If arr[left] == 0, decrement zeroCount.
- Increment left to shrink window.
- While zeroCount > k:
- Update maxLen = max(maxLen, right – left + 1).
- Increment right to expand window.
4. After loop ends, maxLen holds the result.
5. Return maxLen.
Time Complexity: O(n^2)
Space Complexity: O(1)
Code:
#include<iostream>
#include<vector>
using namespace std;
int maxConsecutiveOnesSlidingWindow(vector& arr, int k) {
int left = 0, right = 0;
int zeroCount = 0;
int maxLen = 0;
while (right < arr.size()) { if (arr[right] == 0) zeroCount++; while (zeroCount > k) {
if (arr[left] == 0)
zeroCount--;
left++;
}
maxLen = max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
int main() {
vector arr = {1, 0, 1, 1, 0};
int k = 1;
cout << "Maximum Consecutive Ones (Sliding Window): "
<< maxConsecutiveOnesSlidingWindow(arr, k) << endl;
return 0;
}
}Output:
Maximum Consecutive Ones (Sliding Window): 4
Explanation:
- We maintain a window of valid elements.
- If zeroCount exceeds k → shrink window from the left.
- Keep updating maxLen during iteration.
- Time Complexity: O(n), each element is processed at most twice.
- Space Complexity: O(1), no extra space used.
Final Thoughts:
The problem Maximum Consecutive Ones After Flipping Zeroes is a great exercise to learn array manipulation and sliding window patterns.
We first saw a naive solution that checks all possible subarrays but is inefficient for large inputs. Then, we implemented an optimized approach using Sliding Window, which runs in linear time and works very efficiently.
FAQs
It is a coding problem where you are given a binary array and an integer k. You can flip at most k zeroes to ones. The goal is to find the maximum length of a contiguous subarray that contains only ones after at most k flips.
The Sliding Window technique optimizes this problem to run in O(n) time, while the Naive approach runs in O(n²) time. This makes it much faster and scalable for large arrays.
You should use the Sliding Window approach when you are dealing with problems involving subarrays or substrings with continuous elements and certain constraints (such as number of flips or distinct elements).
Yes, this pattern can be adapted to solve similar problems in non-binary arrays, such as finding the longest subarray with at most K distinct elements or minimum replacements to get continuous characters in strings.
This problem has real-life applications in signal processing, error correction, data compression, and pattern recognition, where sometimes you are allowed a limited number of corrections (flips) to achieve the optimal result.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
