Find zeroes to be flipped so that number of consecutive 1’s is maximized
Given a binary array and an integer m, find the position of zeroes flipping which creates maximum number of consecutive 1’s in array.
Examples :
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
We are allowed to flip maximum 1 zero. If we flip
arr[7], we get 5 consecutive 1's which is maximum
possible under given constraints.
Input: arr[] = {0, 0, 0, 1}
m = 4
Output: 0 1 2
Since m is more than number of zeroes, we can flip
all zeroes.
A Simple Solution is to consider every subarray by running two loops. For every subarray, count number of zeroes in it. Return the maximum size subarray with m or less zeroes. Time Complexity of this solution is O(n2).
A Better Solution is to use auxiliary space to solve the problem in O(n) time.
For all positions of 0’s calculate left[] and right[] which defines the number of consecutive 1’s to the left of i and right of i respectively.
For example, for arr[] = {1, 1, 0, 1, 1, 0, 0, 1, 1, 1} and m = 1, left[2] = 2 and right[2] = 2, left[5] = 2 and right[5] = 0, left[6] = 0 and right[6] = 3.
left[] and right[] can be filled in O(n) time by traversing array once and keeping track of last seen 1 and last seen 0. While filling left[] and right[], we also store indexes of all zeroes in a third array say zeroes[]. For above example, this third array stores {2, 5, 6}
Now traverse zeroes[] and for all consecutive m entries in this array, compute the sum of 1s that can be produced. This step can be done in O(n) using left[] and right[].
Implementation:
C++
// C++ program to find positions of zeroes flipping which // produces maximum number of consecutive 1's #include <bits/stdc++.h> using namespace std; // m is maximum of number zeroes allowed to flip // n is size of array vector< int > maximized_one( int arr[], int n, int m) { // Left array int left[n] = { 0 }; // Right array int right[n] = { 0 }; // Array will contain zeroes position vector< int > zero_pos; // Stores count int count = 0; int previous_index_of_zero = -1; for ( int i = 0; i < n; i++) { if (arr[i]) { count++; } else { left[i] = count; zero_pos.push_back(i); if (previous_index_of_zero != i && previous_index_of_zero != -1) { right[previous_index_of_zero] = count; } count = 0; // To keep track of the previous index of zeroes previous_index_of_zero = i; } } right[previous_index_of_zero] = count; int max_one = -1; vector< int > result_index; int i = 0; while (i <= (zero_pos.size()) - m) { int temp = 0; vector< int > index; for ( int c = 0; c < m; c++) { temp += left[zero_pos[i + c]] + right[zero_pos[i + c]] + 1; // Index is updated index.push_back(zero_pos[i + c]); } // Decrement temp by m-1 because when we are // calculating temp we are adding 1 in it. So, in // order to get exact count of 1. This decrement is // applicable only when value of m is greater than 1 temp = temp - (m - 1); // Updating max value when we get the new max temp // and result_index as well if (temp > max_one) { max_one = temp; result_index = index; } i += 1; } return result_index; } // Driver program int main() { int arr[] = { 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 }; int m = 2; int n = sizeof (arr) / sizeof (arr[0]); cout << "Index of zeroes that are flipped: " ; vector< int > result_index = maximized_one(arr, n, m); for ( auto i : result_index) { cout << i << " " ; } return 0; } |
Java
// Java program to find positions of zeroes flipping which // produces maximum number of consecutive 1's import java.util.*; class GFG{ // m is maximum of number zeroes allowed to flip // n is size of array static Vector<Integer> maximized_one( int arr[], int n, int m) { // Left array int left[] = new int [n]; // Right array int right[] = new int [n]; // Array will contain zeroes position Vector<Integer> zero_pos = new Vector<>(); // Stores count int count = 0 ; int previous_index_of_zero = - 1 ; for ( int i = 0 ; i < n; i++) { if (arr[i]!= 0 ) { count++; } else { left[i] = count; zero_pos.add(i); if (previous_index_of_zero != i && previous_index_of_zero != - 1 ) { right[previous_index_of_zero] = count; } count = 0 ; // To keep track of the previous index of zeroes previous_index_of_zero = i; } } right[previous_index_of_zero] = count; int max_one = - 1 ; Vector<Integer> result_index = new Vector<>(); int i = 0 ; while (i <= (zero_pos.size()) - m) { int temp = 0 ; Vector<Integer> index = new Vector<>(); for ( int c = 0 ; c < m; c++) { temp += left[zero_pos.elementAt(i + c)] + right[zero_pos.elementAt(i + c)] + 1 ; // Index is updated index.add(zero_pos.elementAt(i + c)); } // Decrement temp by m-1 because when we are // calculating temp we are adding 1 in it. So, in // order to get exact count of 1. This decrement is // applicable only when value of m is greater than 1 temp = temp - (m - 1 ); // Updating max value when we get the new max temp // and result_index as well if (temp > max_one) { max_one = temp; result_index = index; } i += 1 ; } return result_index; } // Driver program public static void main(String[] args) { int arr[] = { 1 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 }; int m = 2 ; int n = arr.length; System.out.print( "Index of zeroes that are flipped: [" ); Vector<Integer> result_index = maximized_one(arr, n, m); for ( int i : result_index) { System.out.print(i+ " " ); } System.out.print( "]" ); } } // This code contributed by umadevi9616 |
C#
// C# program to find positions of zeroes flipping which // produces maximum number of consecutive 1's using System; using System.Collections.Generic; public class GFG { // m is maximum of number zeroes allowed to flip // n is size of array static List< int > maximized_one( int []arr, int n, int m) { // Left array int []left = new int [n]; // Right array int []right = new int [n]; // Array will contain zeroes position List< int > zero_pos = new List< int >(); // Stores count int count = 0; int previous_index_of_zero = -1; for ( int j = 0; j < n; j++) { if (arr[j] != 0) { count++; } else { left[j] = count; zero_pos.Add(j); if (previous_index_of_zero != j && previous_index_of_zero != -1) { right[previous_index_of_zero] = count; } count = 0; // To keep track of the previous index of zeroes previous_index_of_zero = j; } } right[previous_index_of_zero] = count; int max_one = -1; List< int > result_index = new List< int >(); int i = 0; while (i <= (zero_pos.Count) - m) { int temp = 0; List< int > index = new List< int >(); for ( int c = 0; c < m; c++) { temp += left[zero_pos[i + c]] + right[zero_pos[i + c]] + 1; // Index is updated index.Add(zero_pos[i + c]); } // Decrement temp by m-1 because when we are // calculating temp we are adding 1 in it. So, in // order to get exact count of 1. This decrement is // applicable only when value of m is greater than 1 temp = temp - (m - 1); // Updating max value when we get the new max temp // and result_index as well if (temp > max_one) { max_one = temp; result_index = index; } i += 1; } return result_index; } // Driver program public static void Main(String[] args) { int []arr = { 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 }; int m = 2; int n = arr.Length; Console.Write( "Index of zeroes that are flipped: [" ); List< int > result_index = maximized_one(arr, n, m); foreach ( int i in result_index) { Console.Write(i+ " " ); } Console.Write( "]" ); } } // This code is contributed by umadevi9616 |
Javascript
<script> // javascript program to find positions of zeroes flipping which // produces maximum number of consecutive 1's // m is maximum of number zeroes allowed to flip // n is size of array function maximized_one(arr, n, m) { // Left array var left = Array(n).fill(0); // Right array var right = Array(n).fill(0); // Array will contain zeroes position var zero_pos = new Array(); // Stores count var count = 0; var previous_index_of_zero = -1; for ( var i = 0; i < n; i++) { if (arr[i] != 0) { count++; } else { left[i] = count; zero_pos.push(i); if (previous_index_of_zero != i && previous_index_of_zero != -1) { right[previous_index_of_zero] = count; } count = 0; // To keep track of the previous index of zeroes previous_index_of_zero = i; } } right[previous_index_of_zero] = count; var max_one = -1; var result_index = Array(); var i = 0; while (i <= (zero_pos.length) - m) { var temp = 0; var index = Array(); for ( var c = 0; c < m; c++) { temp += left[zero_pos[i + c]] + right[zero_pos[i + c]] + 1; // Index is updated index.push(zero_pos[i + c]); } // Decrement temp by m-1 because when we are // calculating temp we are adding 1 in it. So, in // order to get exact count of 1. This decrement is // applicable only when value of m is greater than 1 temp = temp - (m - 1); // Updating max value when we get the new max temp // and result_index as well if (temp > max_one) { max_one = temp; result_index = index; } i += 1; } return result_index; } // Driver program var arr = [ 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 ]; var m = 2; var n = arr.length; document.write( "Index of zeroes that are flipped: [" ); var result_index = maximized_one(arr, n, m); for ( var i = 0; i < result_index.length; i++) { document.write(result_index[i] + " " ); } document.write( "]" ); // This code is contributed by gauravrajput1 </script> |
Python3
# Python3 code for the above approach def maximized_one(arr,n,m): # Left array left = [ 0 ] * n # Right array right = [ 0 ] * n # Array will contain zeroes position zero_pos = [] # Stores count count = 0 previous_index_of_zero = - 1 for i in range (n): if arr[i] = = 1 : count + = 1 if arr[i] = = 0 : left[i] = count zero_pos.append(i) if previous_index_of_zero ! = i and previous_index_of_zero! = - 1 : right[previous_index_of_zero] = count count = 0 # To keep track of the previous index of zeroes previous_index_of_zero = i right[previous_index_of_zero] = count # print(left) # print(right) # print(zero_pos) max_one = - 1 result_index = 0 i = 0 while (i< = len (zero_pos) - m): temp = 0 index = [] for c in range (m): # print(zero_pos[i+c],left[zero_pos[i+c]],right[zero_pos[i+c]]) temp + = left[zero_pos[i + c]] + right[zero_pos[i + c]] + 1 # Index is updated index.append(zero_pos[i + c]) # Decrement temp by m-1 because when we are calculating temp # we are adding 1 in it. # So, in order to get exact count of 1. # This decrement is applicable only when value of m is greater than 1 temp = temp - (m - 1 ) # Updating max value when we get the new max temp # and result_index as well if temp > max_one: max_one = temp result_index = index i + = 1 return result_index # Driver Code if __name__ = = '__main__' : arr = [ 1 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 ] n = len (arr) m = 2 print ( 'Index of zeroes that are flipped: ' ,maximized_one(arr,n,m)) |
Index of zeroes that are flipped: [5, 7]
Time Complexity: O(n)
Auxiliary Space: O(n)
An Efficient Solution can solve the problem in O(n) time and O(1) space. The idea is to use Sliding Window for the given array.
Let us use a window covering from index wL to index wR. Let the number of zeros inside the window be zeroCount. We maintain the window with at most m zeros inside.
The main steps are:
- While zeroCount is no more than m: expand the window to the right (wR++) and update the count zeroCount.
- While zeroCount exceeds m, shrink the window from left (wL++), update zeroCount;
- Update the widest window along the way. The positions of output zeros are inside the best window.
Below is the implementation of the idea.
C++
// C++ program to find positions of zeroes flipping which // produces maximum number of consecutive 1's #include<bits/stdc++.h> using namespace std; // m is maximum of number zeroes allowed to flip // n is size of array void findZeroes( int arr[], int n, int m) { // Left and right indexes of current window int wL = 0, wR = 0; // Left index and size of the widest window int bestL = 0, bestWindow = 0; // Count of zeroes in current window int zeroCount = 0; // While right boundary of current window doesn't cross // right end while (wR < n) { // If zero count of current window is less than m, // widen the window toward right if (zeroCount <= m) { if (arr[wR] == 0) zeroCount++; wR++; } // If zero count of current window is more than m, // reduce the window from left if (zeroCount > m) { if (arr[wL] == 0) zeroCount--; wL++; } // Update widest window if this window size is more if ((wR-wL > bestWindow) && (zeroCount<=m)) { bestWindow = wR-wL; bestL = wL; } } // Print positions of zeroes in the widest window for ( int i=0; i<bestWindow; i++) { if (arr[bestL+i] == 0) cout << bestL+i << " " ; } } // Driver program int main() { int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1}; int m = 2; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Indexes of zeroes to be flipped are " ; findZeroes(arr, n, m); return 0; } |
Java
//Java to find positions of zeroes flipping which // produces maximum number of consecutive 1's class Test { static int arr[] = new int []{ 1 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 1 }; // m is maximum of number zeroes allowed to flip static void findZeroes( int m) { // Left and right indexes of current window int wL = 0 , wR = 0 ; // Left index and size of the widest window int bestL = 0 , bestWindow = 0 ; // Count of zeroes in current window int zeroCount = 0 ; // While right boundary of current window doesn't cross // right end while (wR < arr.length) { // If zero count of current window is less than m, // widen the window toward right if (zeroCount <= m) { if (arr[wR] == 0 ) zeroCount++; wR++; } // If zero count of current window is more than m, // reduce the window from left if (zeroCount > m) { if (arr[wL] == 0 ) zeroCount--; wL++; } // Update widest window if this window size is more if ((wR-wL > bestWindow) && (zeroCount<=m)) { bestWindow = wR-wL; bestL = wL; } } // Print positions of zeroes in the widest window for ( int i= 0 ; i<bestWindow; i++) { if (arr[bestL+i] == 0 ) System.out.print(bestL+i + " " ); } } // Driver method to test the above function public static void main(String[] args) { int m = 2 ; System.out.println( "Indexes of zeroes to be flipped are " ); findZeroes(m); } } |
C#
// C# to find positions of zeroes flipping which // produces maximum number of consecutive 1's using System; class Test { static int []arr = new int []{1, 0, 0, 1, 1, 0, 1, 0, 1, 1}; // m is maximum of number zeroes allowed to flip static void findZeroes( int m) { // Left and right indexes of current window int wL = 0, wR = 0; // Left index and size of the widest window int bestL = 0, bestWindow = 0; // Count of zeroes in current window int zeroCount = 0; // While right boundary of current // window doesn't cross right end while (wR < arr.Length) { // If zero count of current window is less // than m, widen the window toward right if (zeroCount <= m) { if (arr[wR] == 0) zeroCount++; wR++; } // If zero count of current window is more than m, // reduce the window from left if (zeroCount > m) { if (arr[wL] == 0) zeroCount--; wL++; } // Update widest window if this window size is more if ((wR-wL > bestWindow) && (zeroCount<=m)) { bestWindow = wR-wL; bestL = wL; } } // Print positions of zeroes in the widest window for ( int i = 0; i < bestWindow; i++) { if (arr[bestL + i] == 0) Console.Write(bestL + i + " " ); } } // Driver method to test the above function public static void Main(String[] args) { int m = 2; Console.Write( "Indexes of zeroes to be flipped are " ); findZeroes(m); } } // This code is contributed by parashar |
Javascript
<script> // Javascript program to find positions of // zeroes flipping which produces // maximum number of consecutive 1's // m is maximum of number zeroes // allowed to flip n is size of array function findZeroes(arr, n, m) { // Left and right indexes // of current window let wL = 0; let wR = 0; // Left index and size of // the widest window let bestL = 0; let bestWindow = 0; // Count of zeroes in // current window let zeroCount = 0; // While right boundary of // current window doesn't cross // right end while (wR < n) { // If zero count of current // window is less than m, // widen the window toward right if (zeroCount <= m) { if (arr[wR] == 0) zeroCount++; wR++; } // If zero count of current // window is more than m, // reduce the window from left if (zeroCount > m) { if (arr[wL] == 0) zeroCount--; wL++; } // Update widest window if // this window size is more if ((wR - wL > bestWindow) && (zeroCount <= m)) { bestWindow = wR - wL; bestL = wL; } } // Print positions of zeroes // in the widest window for (let i = 0; i < bestWindow; i++) { if (arr[bestL + i] == 0) document.write(bestL + i + " " ); } } // Driver Code let arr = new Array(1, 0, 0, 1, 1, 0, 1, 0, 1, 1); let m = 2; let n = arr.length; document.write( "Indexes of zeroes to be flipped are " ); findZeroes(arr, n, m); // This code is contributed by Saurabh Jaiswal </script> |
PHP
<?php // PHP program to find positions of // zeroes flipping which produces // maximum number of consecutive 1's // m is maximum of number zeroes // allowed to flip n is size of array function findZeroes( $arr , $n , $m ) { // Left and right indexes // of current window $wL = 0; $wR = 0; // Left index and size of // the widest window $bestL = 0; $bestWindow = 0; // Count of zeroes in // current window $zeroCount = 0; // While right boundary of // current window doesn't cross // right end while ( $wR < $n ) { // If zero count of current // window is less than m, // widen the window toward right if ( $zeroCount <= $m ) { if ( $arr [ $wR ] == 0) $zeroCount ++; $wR ++; } // If zero count of current // window is more than m, // reduce the window from left if ( $zeroCount > $m ) { if ( $arr [ $wL ] == 0) $zeroCount --; $wL ++; } // Update widest window if // this window size is more if (( $wR - $wL > $bestWindow ) && ( $zeroCount <= $m )) { $bestWindow = $wR - $wL ; $bestL = $wL ; } } // Print positions of zeroes // in the widest window for ( $i = 0; $i < $bestWindow ; $i ++) { if ( $arr [ $bestL + $i ] == 0) echo $bestL + $i . " " ; } } // Driver Code $arr = array (1, 0, 0, 1, 1, 0, 1, 0, 1, 1); $m = 2; $n = sizeof( $arr )/sizeof( $arr [0]); echo "Indexes of zeroes to be flipped are " ; findZeroes( $arr , $n , $m ); return 0; // This code is contributed by nitin mittal. ?> |
Python3
# Python3 program to find positions # of zeroes flipping which produces # maximum number of consecutive 1's # m is maximum of number zeroes allowed # to flip, n is size of array def findZeroes(arr, n, m) : # Left and right indexes of current window wL = wR = 0 # Left index and size of the widest window bestL = bestWindow = 0 # Count of zeroes in current window zeroCount = 0 # While right boundary of current # window doesn't cross right end while wR < n: # If zero count of current window is less than m, # widen the window toward right if zeroCount < = m : if arr[wR] = = 0 : zeroCount + = 1 wR + = 1 # If zero count of current window is more than m, # reduce the window from left if zeroCount > m : if arr[wL] = = 0 : zeroCount - = 1 wL + = 1 # Update widest window if # this window size is more if (wR - wL > bestWindow) and (zeroCount< = m) : bestWindow = wR - wL bestL = wL # Print positions of zeroes # in the widest window for i in range ( 0 , bestWindow): if arr[bestL + i] = = 0 : print (bestL + i, end = " " ) # Driver program arr = [ 1 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 1 ] m = 2 n = len (arr) print ( "Indexes of zeroes to be flipped are" , end = " " ) findZeroes(arr, n, m) # This code is contributed by Shreyanshi Arun. |
Indexes of zeroes to be flipped are 5 7
Time Complexity: O(N)
Auxiliary Space: O(1)