Find Zeroes to be Flipped, so that Number of Consecutive 1's is Maximised with K Maximum Flips

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;
}

You can also try this code with Online C++ Compiler

Run Code

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!!