Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Observation
3.
Implementation Idea
3.1.
Brute Force
3.2.
Optimised 
4.
Code
5.
Frequently Asked Questions
5.1.
What is a binary array in Java?
5.2.
What is a byte array in Python?
5.3.
What is a memory view in Python?
5.4.
What is the use of bytes and Bytearray in Python?
6.
Conclusion
Last Updated: Mar 27, 2024

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

Introduction 

Let's understand the problem statement first, we are allowed to make k flips at max, and then by flipping some zeros, we want to find the longest sequence of 1s possible. 

Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}, k =3 

Output: 5 7

A maximum of three zeros can be flipped. We receive 8 consecutive 1's if we flip arr[5] and arr[7], which is the maximum allowable under the limitations.

Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}, k = 1

Output: 7

We can only flip one zero at a time. We receive 5 consecutive 1's if we flip arr[7], which is the maximum possible under the limitations.

Observation

Any answer with k-i flips is going to be less than equal to the answer with k flips, which means we can always use k flips and get the most optimal answer. We will use this to make our algorithm. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!!

Live masterclass