## Implementation Idea

### Brute Force

Just make two loops and for each subarray count the values of zeros and ones. Time complexity: O(n2).

### Optimised

A better solution is to solve the problem in O(n) time by using auxiliary space.

Calculate left[] and right[] for all 0's positions, which specify the number of successive 1's to the left and right of I, respectively.

Given arr[] = {1, 1, 0, 1, 1, 0, 0, 1, 1, 1} and k = 1, left[2] = 2 and right[2] = 2, left[5] = 2 and right[5] = 0, left[6] = 0 and right[6] = 3.

By traversing the array once and keeping track of the latest seen 1 and last seen 0, the left[] and right[] can be filled in O(n) time. We also save indexes of all zeroes in a third array called zeroes[] while populating left[] and right[]. This third array stores the numbers 2, 5, and 6 in the previous example.

Now scan zeroes[] and determine the total of 1s that can be produced for all consecutive m items in this array. Using left[] and right[], this step can be completed in O(n) time.

## Code

```
#include <bits/stdc++.h>
using namespace std;
// k is max flips allowed.
// n is size of array
vector<int> zerosIndex(int arr[], int n, int k)
{
// Left array
int left[n] = { 0 };
// Right array
int right[n] = { 0 };
// Array will contain zeroes position
vector<int> zeroPos;
// Stores count
int count = 0;
int previousZeroIndex = -1;
for (int i = 0; i < n; i++) {
if (arr[i]) {
count++;
}
else {
left[i] = count;
zeroPos.push_back(i);
if (previousZeroIndex != i
&& previousZeroIndex != -1) {
right[previousZeroIndex] = count;
}
count = 0;
// here we keep track of the previous index of zeroes
previousZeroIndex = i;
}
}
right[previousZeroIndex] = count;
int max_one = -1;
vector<int> resultIndex;
int i = 0;
while (i <= (zeroPos.size()) - m) {
int temp = 0;
vector<int> index;
for (int c = 0; c < m; c++) {
temp += left[zeroPos[i + c]]
+ right[zeroPos[i + c]] + 1;
// Index is updated
index.push_back(zeroPos[i + c]);
}
// Because we are adding 1 to the temp
// when we calculate it, we must reduce it by m-1.
// As a result, in order to get a precise count of 1,
// Only when the value of m is greater than 1 does this decrease apply.
temp = temp - (m - 1);
// updating max
// and resultIndex as well
if (temp > max_one) {
max_one = temp;
resultIndex = index;
}
i += 1;
}
return resultIndex;
}
```

Also see, __Rabin Karp Algorithm__

## Frequently Asked Questions

#### What is a binary array in Java?

The binary array set is a space-saving data structure that allows you to easily add elements and validate membership. It essentially functions as a set of sorted arrays with power-of-2 sizes.

#### What is a byte array in Python?

bytearray() method returns a bytearray object which is an array of given bytes. It gives a mutable sequence of integers in the range 0 <= x < 256. Syntax: bytearray(source, encoding, errors)

#### What is a memory view in Python?

In Python, a memory view is a safe way to expose the buffer protocol. By constructing a memory view object, you can access an object's internal buffers.

#### What is the use of bytes and Bytearray in Python?

The bytes and bytearray classes in Python 3 both store arrays of bytes, with each byte having a value between 0 and 255. The main difference is that a bytes object is immutable, which means that once formed, its elements cannot be changed. A bytearray object, on the other hand, permits you to change its elements.

## Conclusion

So in this article, we learnt how to find the position of zeroes to be flipped so that number of consecutive 1’s is maximised with k maximum flips.

Check out our __Coding Ninjas Studio__ __Guided Path__ to learn about __Data Structures and Algorithms__, __Competitive Programming__, __JavaScript__, __System Design__, and more, Take a look at the mock __test series__ and participate in the __contests__ hosted by Coding Ninjas Studio if you want to improve your coding skills. If you are new to preparation and want to work for firms such as Amazon, Microsoft, Uber, and others, you should review the __problems__, __interview experiences,__ and __interview bundle__ for placement preparations.

Consider taking one of our paid __courses __to give yourself and your profession an edge!

Please vote for our blogs if you find them valuable and exciting.

Happy Learning!!