Find the largest rectangle of 1 's with swapping of columns allowed | Python 3 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
R = 3 NEW_LINE C = 5 NEW_LINE def maxArea ( mat ) : NEW_LINE INDENT hist = [ [ 0 for i in range ( C + 1 ) ] for i in range ( R + 1 ) ] NEW_LINE for i in range ( 0 , C , 1 ) : NEW_LINE INDENT hist [ 0 ] [ i ] = mat [ 0 ] [ i ] NEW_LINE for j in range ( 1 , R , 1 ) : NEW_LINE INDENT if ( ( mat [ j ] [ i ] == 0 ) ) : NEW_LINE INDENT hist [ j ] [ i ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT hist [ j ] [ i ] = hist [ j - 1 ] [ i ] + 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 0 , R , 1 ) : NEW_LINE INDENT count = [ 0 for i in range ( R + 1 ) ] NEW_LINE for j in range ( 0 , C , 1 ) : NEW_LINE INDENT count [ hist [ i ] [ j ] ] += 1 NEW_LINE DEDENT col_no = 0 NEW_LINE j = R NEW_LINE while ( j >= 0 ) : NEW_LINE INDENT if ( count [ j ] > 0 ) : NEW_LINE INDENT for k in range ( 0 , count [ j ] , 1 ) : NEW_LINE INDENT hist [ i ] [ col_no ] = j NEW_LINE col_no += 1 NEW_LINE DEDENT DEDENT j -= 1 NEW_LINE DEDENT DEDENT max_area = 0 NEW_LINE for i in range ( 0 , R , 1 ) : NEW_LINE INDENT for j in range ( 0 , C , 1 ) : NEW_LINE INDENT curr_area = ( j + 1 ) * hist [ i ] [ j ] NEW_LINE if ( curr_area > max_area ) : NEW_LINE INDENT max_area = curr_area NEW_LINE DEDENT DEDENT DEDENT return max_area NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 0 , 1 , 0 , 1 , 0 ] , [ 0 , 1 , 0 , 1 , 1 ] , [ 1 , 1 , 0 , 1 , 0 ] ] NEW_LINE print ( " Area ▁ of ▁ the ▁ largest ▁ rectangle ▁ is " , maxArea ( mat ) ) NEW_LINE DEDENT