Find Zeros to be Flipped so that number of Consecutive 1’s is maximized

January 29, 2021

Find Zeros to be Flipped so that number of Consecutive 1’s is maximized in Java.

Problem Statement:

Given a binary array and number of zeros to be flipped, write a program to find the zeros that need to be flipped so that the number of consecutive 1’s is maximized.

Example:

INPUT:
arr[] = {0, 1, 0, 1, 1, 0, 1}
zeroes= 2

OUTPUT:
The indexes are 2, 5

Algorithm:

Initialize a variable count to keep track of number of zeros
Till the right pointer of the window is less than the input array
If the count is less than the input number of zeros, then increase the window size to the right and if we find any zero increment the count value
If the count is greater than the input number of zeros, then decrease the window size from the left and if we find any zero decrement the count value
If the window size is greater than the previous window size make it as the best window.
Print the zeros indexes in the best window.

Java code :

class prepinsta 
{ 
    static int arr[] = new int[]{0, 1, 0, 1, 1, 0, 1}; 
      
  
    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 (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 + ” “); 
        } 
    } 
      
    
    public static void main(String[] args)  
    { 
        int m = 2; 
        System.out.println(“Indexes of zeroes to be flipped are “); 
          
        findZeroes(m); 
    } 
} 

Output:

Indexes of zeroes to be flipped are 2 5