Maximum perimeter of a square in a 2D grid | Java implementation of the approach ; 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
import java . util . * ; class GFG { static void perfix_calculate ( int [ ] [ ] A , int [ ] [ ] row , int [ ] [ ] col ) { int n = ( int ) A . length ; int m = ( int ) A [ 0 ] . length ; for ( int i = 0 ; i < n ; ++ i ) { row [ i ] [ 0 ] = A [ i ] [ 0 ] ; } for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 1 ; j < m ; ++ j ) { row [ i ] [ j ] = row [ i ] [ j - 1 ] + A [ i ] [ j ] ; } } for ( int i = 0 ; i < m ; ++ i ) { col [ 0 ] [ i ] = A [ 0 ] [ i ] ; } for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 1 ; j < n ; ++ j ) { col [ j ] [ i ] = A [ j ] [ i ] + col [ j - 1 ] [ i ] ; } } } static int perimeter ( int i , int j , int k , int [ ] [ ] row , int [ ] [ ] col , int [ ] [ ] A ) { int 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 ] ; int upper_row = row [ i ] [ j + k ] - row_s ; int 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 ] ; int lower_row = row [ i + k ] [ j + k ] - row_s ; int right_col = col [ i + k ] [ j + k ] - col_s ; int 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 ; } static int maxPerimeter ( int [ ] [ ] A ) { int n = ( int ) A . length ; int m = ( int ) A [ 0 ] . length ; int [ ] [ ] row = new int [ n ] [ m ] ; int [ ] [ ] col = new int [ n ] [ m ] ; perfix_calculate ( A , row , col ) ; int maxPer = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < m ; ++ j ) { for ( int k = 0 ; k < Math . min ( n - i , m - j ) ; ++ k ) { int perimtr = perimeter ( i , j , k , row , col , A ) ; maxPer = Math . max ( maxPer , perimtr ) ; } } } return maxPer ; } public static void main ( String [ ] args ) { int [ ] [ ] A = { { 1 , 1 , 0 } , { 1 , 1 , 1 } , { 0 , 1 , 1 } } ; System . out . print ( maxPerimeter ( A ) ) ; } }