Check whether row or column swaps produce maximum size binary sub | Java program to find maximum binary sub - matrix with row swaps and column swaps . ; Precompute the number of consecutive 1 below the ( i , j ) in j - th column and the number of consecutive 1 s on right side of ( i , j ) in i - th row . ; Travesing the 2d matrix from top - right . ; If ( i , j ) contain 0 , do nothing ; } Counting consecutive 1 on right side ; Travesing the 2d matrix from bottom - left . ; If ( i , j ) contain 0 , do nothing ; } Counting consecutive 1 down to ( i , j ) . ; Return maximum size submatrix with row swap allowed . ; Copying the column ; Sort the copied array ; Find maximum submatrix size . ; Return maximum size submatrix with column swap allowed . ; Copying the row . ; Sort the copied array ; Find maximum submatrix size . ; Solving for row swap and column swap ; Comparing both . ; Driven Program
import java . util . Arrays ; class GFG { static int R = 5 ; static int C = 3 ; static void precompute ( int mat [ ] [ ] , int ryt [ ] [ ] , int dwn [ ] [ ] ) { for ( int j = C - 1 ; j >= 0 ; j -- ) { for ( int i = 0 ; i < R ; ++ i ) { if ( mat [ i ] [ j ] == 0 ) { ryt [ i ] [ j ] = 0 ; else { ryt [ i ] [ j ] = ryt [ i ] [ j + 1 ] + 1 ; } } } for ( int i = R - 1 ; i >= 0 ; i -- ) { for ( int j = 0 ; j < C ; ++ j ) { if ( mat [ i ] [ j ] == 0 ) { dwn [ i ] [ j ] = 0 ; else { dwn [ i ] [ j ] = dwn [ i + 1 ] [ j ] + 1 ; } } } } static int solveRowSwap ( int ryt [ ] [ ] ) { int b [ ] = new int [ R ] , ans = 0 ; for ( int j = 0 ; j < C ; j ++ ) { for ( int i = 0 ; i < R ; i ++ ) { b [ i ] = ryt [ i ] [ j ] ; } Arrays . sort ( b ) ; for ( int i = 0 ; i < R ; ++ i ) { ans = Math . max ( ans , b [ i ] * ( R - i ) ) ; } } return ans ; } static int solveColumnSwap ( int dwn [ ] [ ] ) { int b [ ] = new int [ C ] , ans = 0 ; for ( int i = 0 ; i < R ; ++ i ) { for ( int j = 0 ; j < C ; ++ j ) { b [ j ] = dwn [ i ] [ j ] ; } Arrays . sort ( b ) ; for ( int k = 0 ; k < C ; ++ k ) { ans = Math . max ( ans , b [ k ] * ( C - k ) ) ; } } return ans ; } static void findMax1s ( int mat [ ] [ ] ) { int ryt [ ] [ ] = new int [ R + 2 ] [ C + 2 ] , dwn [ ] [ ] = new int [ R + 2 ] [ C + 2 ] ; precompute ( mat , ryt , dwn ) ; int rswap = solveRowSwap ( ryt ) ; int cswap = solveColumnSwap ( dwn ) ; if ( rswap > cswap ) { System . out . println ( "Row SwapNEW_LINE" + rswap); } else { System . out . println ( "Column SwapNEW_LINE" + cswap); } } public static void main ( String [ ] args ) { int mat [ ] [ ] = { { 0 , 0 , 0 } , { 1 , 1 , 0 } , { 1 , 1 , 0 } , { 0 , 0 , 0 } , { 1 , 1 , 0 } } ; findMax1s ( mat ) ; } }