Largest square sub | Define the prefix sum arrays globally ; Diagonal sum ; Check each row ; Check each column ; Check anti - diagonal ; Store the size of the given grid ; Compute the prefix sum for the rows ; Compute the prefix sum for the columns ; Check for all possible square submatrix ; Driver Code
let prefix_sum_row = new Array ( 50 ) ; for ( let i = 0 ; i < prefix_sum_row . length ; i ++ ) { prefix_sum_row [ i ] = new Array ( 51 ) . fill ( 0 ) ; } let prefix_sum_col = new Array ( 50 ) ; for ( let i = 0 ; i < prefix_sum_col . length ; i ++ ) { prefix_sum_col [ i ] = new Array ( 51 ) . fill ( 0 ) ; } function is_valid ( r , c , size , grid ) { let r_end = r + size , c_end = c + size ; let sum = 0 ; for ( let i = r , j = c ; i < r_end ; i ++ , j ++ ) { sum += grid [ i ] [ j ] ; } for ( let i = r ; i < r_end ; i ++ ) { if ( prefix_sum_row [ i ] [ c_end ] - prefix_sum_row [ i ] != sum ) { return false ; } } for ( let i = c ; i < c_end ; i ++ ) { if ( prefix_sum_col [ r_end ] [ i ] - prefix_sum_col [ r ] [ i ] != sum ) { return false ; } } let ad_sum = 0 ; for ( let i = r , j = c_end - 1 ; i < r_end ; i ++ , j -- ) { ad_sum += grid [ i ] [ j ] ; } return ad_sum == sum ; } function largestSquareValidMatrix ( grid ) { let m = grid . length , n = grid [ 0 ] . length ; for ( let i = 0 ; i < m ; i ++ ) { for ( let j = 1 ; j <= n ; j ++ ) { prefix_sum_row [ i ] [ j ] = prefix_sum_row [ i ] [ j - 1 ] + grid [ i ] [ j - 1 ] ; } } for ( let i = 1 ; i <= m ; i ++ ) { for ( let j = 0 ; j < n ; j ++ ) { prefix_sum_col [ i ] [ j ] = prefix_sum_col [ i - 1 ] [ j ] + grid [ i - 1 ] [ j ] ; } } for ( let size = Math . min ( m , n ) ; size > 1 ; size -- ) { for ( let i = 0 ; i <= m - size ; i ++ ) { for ( let j = 0 ; j <= n - size ; j ++ ) { if ( is_valid ( i , j , size , grid ) ) { return size ; } } } } return 1 ; } let grid = [ [ 7 , 1 , 4 , 5 , 6 ] , [ 2 , 5 , 1 , 6 , 4 ] , [ 1 , 5 , 4 , 3 , 2 ] , [ 1 , 2 , 7 , 3 , 4 ] ] ; document . write ( largestSquareValidMatrix ( grid ) ) ;