Find Zeros to be Flipped so that number of Consecutive 1’s is maximized

Given a binary array and number of zeros to be flipped, write a program to find the zeros that needs to be flipped so that the number of consecutive 1’s is maximized


arr[] = {0, 1, 0, 1, 1, 0, 1}
zeroes= 2

The indexes are 2, 5

In the above example, we can see that when the zeroes at indexes 2 and 5 are flipped we get maximum  number of consecutiive one’s.

Time Complexity : O(n)

In this method the main idea is using the sliding window


1. Initialize a variable count to keep track of number of zeros

2. Till the right pointer of the window is less than the input array

3. If the count is less than the input number of zeros, then increase the window size to the right and if we find any   zero increment the count value

4. If the count is greater than the input number of zeros, then decrease the window size from the left and if we find any zero decrement the count value

5. If the window size is greater than the previous window size make it as the best window.

6. Print the zeros indexes in the best window.

C++ Program

#include <bits/stdc++.h>
using namespace std;

void zeroesIndexes(int arr[],int zeroes, int n) //this function prints the zero index that should be flipped
	int start =0, end = 0; //starting and ending of the window
	int count =0; //number of zeros in window
	int bestwindow =0, bestwindowstart= 0;// bestwindow size and starting point
		if(count <= zeroes) //if no of zeros is less than input zeros
			end++;		//increasing window size
		if(count > zeroes) //if no of zeros greater than input zeroes
			start++;          //decreasing window size
		if(end-start > bestwindow) //updating the best window
			bestwindow = end-start;
			bestwindowstart = start;
	cout<<"The indexes are ";	
	for (int i = bestwindowstart; i < bestwindow; ++i)
			cout<< i<<" ";
int main()
	int arr[] = {0, 1, 0, 1, 1, 0, 1};
	int zeroes= 2;				 //no of zeroes that can be flipped	
	int n = sizeof(arr)/sizeof(arr[0]);
	zeroesIndexes(arr, zeroes, n);
	return 0;
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup