# Find k zeroes to be flipped so that number of consecutive 1’s is maximized

• Given a binary array and an integer k, find the position of zeroes flipping which creates maximum number of consecutive 1s in array.

Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
m = 2
Output: 5 7
We are allowed to flip maximum 2 zeroes. If we flip
arr[5] and arr[7], we get 8 consecutive 1's which is
maximum possible under given constraints

Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
m = 1
Output: 7

Input: arr[] = {0, 0, 0, 1}
m = 4
Output: 0 1 2

• CPP solution: I think there is a better solution to this problem. The complexity of this solution is O(n^2) worst case. For every zero in an array, I am checking for both if it's modified and if it's not modified. Suggestions?

``````#include "stdio.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution{
public:
vector<int> findZeros(vector<int>& nums, int m){
vector<int> res;
if(m==0 || nums.size()==0)return res;
findZeros(nums,m,0,res,0);
return sol;
}

private:
int max_ones = 0;
vector<int> sol; // value to be returned
void findZeros(vector<int>& nums, int m, int ones, vector<int> ret,int index){
if(index>=nums.size()-1){
if(ones>max_ones){
max_ones = ones;
sol = ret;
}
return;
}
while(nums[index]!=0 && index<nums.size()-1){
index++;
ones++;
}
if(m>0 && nums[index]==0){
ret.push_back(index);
findZeros(nums,m-1, ones, ret, index+1);
ret.pop_back();
}
if(nums[index]==0)
findZeros(nums,m,0,ret,index+1);
else
findZeros(nums,m,ones,ret,index+1);
return;
}
}solution;

int main(){
vector<int> nums = {1,0,0,1,1,0,1,0,1,1,1};
vector<int> ans = solution.findZeros(nums,2);
for(int num:ans) cout << num << " " ;
return 0;
}
``````

• you can use sliding window concept. complexity will be O(n).

``````#include<iostream>
using namespace std;

int main()
{
int max;
int n=11;
int arr[]={1,0,0,1,1,0,1,0,1,1,1};
for (int j=0;j<2;j++)
{
int count=0;
int sum1=0;
max=0;
int position;
int final_position;
for (int i=0;i<n;i++)
{

if (arr[i]==1){
if (sum1==0) {
position=i;
}
sum1=sum1+1;
}

if (arr[i]==0 || i==n-1)
{
if (sum1>max) {
final_position=position;
max=sum1;
}
sum1=0;
}
}
arr[final_position-1]=1;
cout<<final_position-1<<endl;
}
}
``````

• As suggested above, a sliding window can give O(n) performance. The keys to note are 1) if you reach a zero and can flip it, do so because that's the only way to extend the run of consecutive ones, 2) if you reach a zero and cannot flip it, see if undoing the first flip is better or not. I did not find a way to handle (maxFlips == 0) gracefully.

``````#include <deque>
#include <vector>

struct Memo
{
std::size_t flippedIndex;

// Number of ones lost if this index is unflipped.
std::size_t consecutiveOnes;

Memo(const std::size_t flippedIndex, const std::size_t consecutiveOnes)
: flippedIndex(flippedIndex), consecutiveOnes(consecutiveOnes)
{
}
};

std::size_t getFlipIndexes(const std::vector<int>& values,
const std::size_t maxFlips, const std::size_t usedFlips,
const std::size_t i, const std::size_t consecutiveOnes,
std::deque<Memo>& memos, std::size_t& lastIndex)
{
// Avoid recursion for runs of ones.
std::size_t j = i;
for (; j < values.size(); ++j)
{
if (values[j] != 1) break;
}
const std::size_t onesFromI = j - i;
if (j == values.size())
{
lastIndex = j;
return consecutiveOnes + onesFromI;
}

if (maxFlips > usedFlips)
{
// Flip values[j] so there are a bunch of + 1 coming up.
const std::size_t onesLost = (memos.empty())
? consecutiveOnes + onesFromI + 1
: j - memos.back().flippedIndex;
memos.push_back(Memo(j, onesLost));
return getFlipIndexes(values, maxFlips, usedFlips + 1, j + 1,
consecutiveOnes + onesFromI + 1, memos, lastIndex);
}

if (!memos.empty())
{
// Unflip the first one and recurse from j.
const Memo removed = memos.front();
memos.pop_front();
const std::size_t rConsecutiveOnes = getFlipIndexes(values, maxFlips,
usedFlips - 1, j,
consecutiveOnes + onesFromI - removed.consecutiveOnes, memos,
lastIndex);
if (rConsecutiveOnes > (consecutiveOnes + onesFromI))
{
return rConsecutiveOnes;
}
// Unflipping was not better so reflip.
memos.push_front(removed);
}
lastIndex = j;
return consecutiveOnes + onesFromI;
}

std::vector<std::size_t> getFlipIndexes(const std::vector<int>& values,
const std::size_t maxFlips, std::size_t& consecutiveOnes)
{
std::deque<Memo> maxMemos;
std::size_t maxConsecutiveOnes = 0;

// The while loop will only execute once as long as (maxFlips > 0).
std::size_t lastIndex = 0;
while (lastIndex < (values.size() - 1))
{
std::deque<Memo> memos;
consecutiveOnes = getFlipIndexes(values, maxFlips, 0, lastIndex, 0, memos,
lastIndex);
if (consecutiveOnes > maxConsecutiveOnes)
{
maxConsecutiveOnes = consecutiveOnes;
maxMemos.clear();
maxMemos.swap(memos);
}

// Special case for (maxFlips == 0) && (values[lastIndex] == 0).
if (0 == consecutiveOnes)
{
++lastIndex;
}
}

std::vector<std::size_t> indexes;
for (auto memo : maxMemos)
{
indexes.push_back(memo.flippedIndex);
}
consecutiveOnes = maxConsecutiveOnes;
return indexes;
}

void main()
{
const std::vector<int> input = { 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 };
const std::size_t maxFlips = 2;
//const std::vector<int> input = { 0, 0, 0, 1 };
//const std::size_t maxFlips = 1;

std::size_t consecutiveOnes;
auto indexes = getFlipIndexes(input, maxFlips, consecutiveOnes);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.