Find the largest rectangle of 1 's with swapping of columns allowed | Java program to find the largest rectangle of 1 's with swapping of columns allowed. ; Returns area of the largest rectangle of 1 's ; An auxiliary array to store count of consecutive 1 's  in every column. ; Step 1 : Fill the auxiliary array hist [ ] [ ] ; First row in hist [ ] [ ] is copy of first row in mat [ ] [ ] ; Fill remaining rows of hist [ ] [ ] ; Step 2 : Sort rows of hist [ ] [ ] in non - increasing order ; counting occurrence ; Traverse the count array from right side ; Step 3 : Traverse the sorted hist [ ] [ ] to find maximum area ; Since values are in decreasing order , The area ending with cell ( i , j ) can be obtained by multiplying column number with value of hist [ i ] [ j ] ; Driver Code
class GFG { static final int R = 3 ; static final int C = 5 ; static int maxArea ( int mat [ ] [ ] ) { int hist [ ] [ ] = new int [ R + 1 ] [ C + 1 ] ; for ( int i = 0 ; i < C ; i ++ ) { hist [ 0 ] [ i ] = mat [ 0 ] [ i ] ; for ( int j = 1 ; j < R ; j ++ ) { hist [ j ] [ i ] = ( mat [ j ] [ i ] == 0 ) ? 0 : hist [ j - 1 ] [ i ] + 1 ; } } for ( int i = 0 ; i < R ; i ++ ) { int count [ ] = new int [ R + 1 ] ; for ( int j = 0 ; j < C ; j ++ ) { count [ hist [ i ] [ j ] ] ++ ; } int col_no = 0 ; for ( int j = R ; j >= 0 ; j -- ) { if ( count [ j ] > 0 ) { for ( int k = 0 ; k < count [ j ] ; k ++ ) { hist [ i ] [ col_no ] = j ; col_no ++ ; } } } } int curr_area , max_area = 0 ; for ( int i = 0 ; i < R ; i ++ ) { for ( int j = 0 ; j < C ; j ++ ) { curr_area = ( j + 1 ) * hist [ i ] [ j ] ; if ( curr_area > max_area ) { max_area = curr_area ; } } } return max_area ; } public static void main ( String [ ] args ) { int mat [ ] [ ] = { { 0 , 1 , 0 , 1 , 0 } , { 0 , 1 , 0 , 1 , 1 } , { 1 , 1 , 0 , 1 , 0 } } ; System . out . println ( " Area ▁ of ▁ the ▁ largest ▁ rectangle ▁ is ▁ " + maxArea ( mat ) ) ; } }