Maximum perimeter of a square in a 2D grid | Function to calculate the perfix sum of the rows and the columns of the given matrix ; Number of rows and cols ; First column of the row prefix array ; Update the prefix sum for the rows ; First row of the column prefix array ; Update the prefix sum for the columns ; Function to return the perimeter of the square having top - left corner at ( i , j ) and size k ; i and j represent the top left corner of the square and k is the size ; Get the upper row sum ; Get the left column sum ; At the distance of k in both direction ; The perimeter will be sum of all the values ; Since all the corners are included twice , they need to be subtract from the sum ; Function to return the maximum perimeter of a square in the given matrix ; Number of rows and cols ; Function call to calculate the prefix sum of rows and cols ; To store the maximum perimeter ; Nested loops to choose the top - left corner of the square ; Loop for the size of the square ; Get the perimeter of the current square ; Update the maximum perimeter so far ; Driver code
def perfix_calculate ( A , row , col ) : NEW_LINE INDENT n = len ( A ) NEW_LINE m = len ( A [ 0 ] ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT row [ i ] [ 0 ] = A [ i ] [ 0 ] NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( 1 , m ) : NEW_LINE INDENT row [ i ] [ j ] = row [ i ] [ j - 1 ] + A [ i ] [ j ] NEW_LINE DEDENT DEDENT for i in range ( m ) : NEW_LINE INDENT col [ 0 ] [ i ] = A [ 0 ] [ i ] NEW_LINE DEDENT for i in range ( m ) : NEW_LINE INDENT for j in range ( 1 , m ) : NEW_LINE INDENT col [ j ] [ i ] = A [ j ] [ i ] + col [ j - 1 ] [ i ] NEW_LINE DEDENT DEDENT DEDENT def perimeter ( i , j , k , row , col , A ) : NEW_LINE INDENT row_s , col_s = 0 , 0 NEW_LINE if ( j == 0 ) : NEW_LINE INDENT row_s = 0 NEW_LINE DEDENT else : NEW_LINE INDENT row_s = row [ i ] [ j - 1 ] NEW_LINE DEDENT if ( i == 0 ) : NEW_LINE INDENT col_s = 0 NEW_LINE DEDENT else : NEW_LINE INDENT col_s = col [ i - 1 ] [ j ] NEW_LINE DEDENT upper_row = row [ i ] [ j + k ] - row_s NEW_LINE left_col = col [ i + k ] [ j ] - col_s NEW_LINE if ( j == 0 ) : NEW_LINE INDENT row_s = 0 NEW_LINE DEDENT else : NEW_LINE INDENT row_s = row [ i + k ] [ j - 1 ] NEW_LINE DEDENT if ( i == 0 ) : NEW_LINE INDENT col_s = 0 NEW_LINE DEDENT else : NEW_LINE INDENT col_s = col [ i - 1 ] [ j + k ] NEW_LINE DEDENT lower_row = row [ i + k ] [ j + k ] - row_s NEW_LINE right_col = col [ i + k ] [ j + k ] - col_s NEW_LINE sum = upper_row + lower_row + left_col + right_col NEW_LINE sum -= ( A [ i ] [ j ] + A [ i + k ] [ j ] +   \ A [ i ] [ j + k ] + A [ i + k ] [ j + k ] ) NEW_LINE return sum NEW_LINE DEDENT def maxPerimeter ( A ) : NEW_LINE INDENT n = len ( A ) NEW_LINE m = len ( A [ 0 ] ) NEW_LINE row = [ [ 0 for i in range ( m ) ] for i in range ( n ) ] NEW_LINE col = [ [ 0 for i in range ( m ) ] for i in range ( n ) ] NEW_LINE perfix_calculate ( A , row , col ) NEW_LINE maxPer = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT for k in range ( min ( n - i , m - j ) ) : NEW_LINE INDENT perimtr = perimeter ( i , j , k , row , col , A ) NEW_LINE maxPer = max ( maxPer , perimtr ) NEW_LINE DEDENT DEDENT DEDENT return maxPer NEW_LINE DEDENT A = [ [ 1 , 1 , 0 ] , [ 1 , 1 , 1 ] , [ 0 , 1 , 1 ] ] NEW_LINE print ( maxPerimeter ( A ) ) NEW_LINE