Check whether row or column swaps produce maximum size binary sub | Python3 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 . ; Driver Code
R , C = 5 , 3 NEW_LINE def precompute ( mat , ryt , dwn ) : NEW_LINE INDENT for j in range ( C - 1 , - 1 , - 1 ) : NEW_LINE INDENT for i in range ( 0 , R ) : NEW_LINE INDENT if mat [ i ] [ j ] == 0 : NEW_LINE INDENT ryt [ i ] [ j ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT ryt [ i ] [ j ] = ryt [ i ] [ j + 1 ] + 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( R - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( 0 , C ) : NEW_LINE INDENT if mat [ i ] [ j ] == 0 : NEW_LINE INDENT dwn [ i ] [ j ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT dwn [ i ] [ j ] = dwn [ i + 1 ] [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def solveRowSwap ( ryt ) : NEW_LINE INDENT b = [ 0 ] * R NEW_LINE ans = 0 NEW_LINE for j in range ( 0 , C ) : NEW_LINE INDENT for i in range ( 0 , R ) : NEW_LINE INDENT b [ i ] = ryt [ i ] [ j ] NEW_LINE DEDENT b . sort ( ) NEW_LINE for i in range ( 0 , R ) : NEW_LINE INDENT ans = max ( ans , b [ i ] * ( R - i ) ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def solveColumnSwap ( dwn ) : NEW_LINE INDENT b = [ 0 ] * C NEW_LINE ans = 0 NEW_LINE for i in range ( 0 , R ) : NEW_LINE INDENT for j in range ( 0 , C ) : NEW_LINE INDENT b [ j ] = dwn [ i ] [ j ] NEW_LINE DEDENT b . sort ( ) NEW_LINE for i in range ( 0 , C ) : NEW_LINE INDENT ans = max ( ans , b [ i ] * ( C - i ) ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def findMax1s ( mat ) : NEW_LINE INDENT ryt = [ [ 0 for i in range ( C + 2 ) ] for j in range ( R + 2 ) ] NEW_LINE dwn = [ [ 0 for i in range ( C + 2 ) ] for j in range ( R + 2 ) ] NEW_LINE precompute ( mat , ryt , dwn ) NEW_LINE rswap = solveRowSwap ( ryt ) NEW_LINE cswap = solveColumnSwap ( dwn ) NEW_LINE if rswap > cswap : print ( " Row Swap " , rswap ) NEW_LINE else : print ( " Column Swap " , cswap ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT mat = [ [ 0 , 0 , 0 ] , [ 1 , 1 , 0 ] , [ 1 , 1 , 0 ] , [ 0 , 0 , 0 ] , [ 1 , 1 , 0 ] ] NEW_LINE findMax1s ( mat ) NEW_LINE DEDENT