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
function perfix_calculate ( A , row , col ) { let n = A . length ; let m = A [ 0 ] . length ; for ( let i = 0 ; i < n ; ++ i ) { row [ i ] [ 0 ] = A [ i ] [ 0 ] ; } for ( let i = 0 ; i < n ; ++ i ) { for ( let j = 1 ; j < m ; ++ j ) { row [ i ] [ j ] = row [ i ] [ j - 1 ] + A [ i ] [ j ] ; } } for ( let i = 0 ; i < m ; ++ i ) { col [ 0 ] [ i ] = A [ 0 ] [ i ] ; } for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 1 ; j < n ; ++ j ) { col [ j ] [ i ] = A [ j ] [ i ] + col [ j - 1 ] [ i ] ; } } } function perimeter ( i , j , k , row , col , A ) { let row_s , col_s ; if ( j == 0 ) row_s = 0 ; else row_s = row [ i ] [ j - 1 ] ; if ( i == 0 ) col_s = 0 ; else col_s = col [ i - 1 ] [ j ] ; let upper_row = row [ i ] [ j + k ] - row_s ; let left_col = col [ i + k ] [ j ] - col_s ; if ( j == 0 ) row_s = 0 ; else row_s = row [ i + k ] [ j - 1 ] ; if ( i == 0 ) col_s = 0 ; else col_s = col [ i - 1 ] [ j + k ] ; let lower_row = row [ i + k ] [ j + k ] - row_s ; let right_col = col [ i + k ] [ j + k ] - col_s ; let sum = upper_row + lower_row + left_col + right_col ; sum -= ( A [ i ] [ j ] + A [ i + k ] [ j ] + A [ i ] [ j + k ] + A [ i + k ] [ j + k ] ) ; return sum ; } function maxPerimeter ( A ) { let n = A . length ; let m = A [ 0 ] . length ; let row = new Array ( n ) ; let col = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { row [ i ] = new Array ( m ) ; col [ i ] = new Array ( m ) ; } perfix_calculate ( A , row , col ) ; let maxPer = 0 ; for ( let i = 0 ; i < n ; ++ i ) { for ( let j = 0 ; j < m ; ++ j ) { for ( let k = 0 ; k < Math . min ( n - i , m - j ) ; ++ k ) { let perimtr = perimeter ( i , j , k , row , col , A ) ; maxPer = Math . max ( maxPer , perimtr ) ; } } } return maxPer ; } let A = [ [ 1 , 1 , 0 ] , [ 1 , 1 , 1 ] , [ 0 , 1 , 1 ] ] ; document . write ( maxPerimeter ( A ) ) ;