Largest square sub | C # program for the above approach ; 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
using System ; class GFG { public static int [ , ] prefix_sum_row = new int [ 50 , 51 ] ; public static int [ , ] prefix_sum_col = new int [ 51 , 50 ] ; public static bool is_valid ( int r , int c , int size , int [ , ] grid ) { int r_end = r + size , c_end = c + size ; int sum = 0 ; for ( int i = r , j = c ; i < r_end ; i ++ , j ++ ) { sum += grid [ i , j ] ; } for ( int i = r ; i < r_end ; i ++ ) { if ( prefix_sum_row [ i , c_end ] - prefix_sum_row [ i , c ] != sum ) { return false ; } } for ( int i = c ; i < c_end ; i ++ ) { if ( prefix_sum_col [ r_end , i ] - prefix_sum_col [ r , i ] != sum ) { return false ; } } int ad_sum = 0 ; for ( int i = r , j = c_end - 1 ; i < r_end ; i ++ , j -- ) { ad_sum += grid [ i , j ] ; } return ad_sum == sum ; } public static int largestSquareValidMatrix ( int [ , ] grid ) { int m = grid . GetLength ( 0 ) , n = grid . GetLength ( 1 ) ; for ( int i = 0 ; i < m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { prefix_sum_row [ i , j ] = prefix_sum_row [ i , j - 1 ] + grid [ i , j - 1 ] ; } } for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { prefix_sum_col [ i , j ] = prefix_sum_col [ i - 1 , j ] + grid [ i - 1 , j ] ; } } for ( int size = Math . Min ( m , n ) ; size > 1 ; size -- ) { for ( int i = 0 ; i <= m - size ; i ++ ) { for ( int j = 0 ; j <= n - size ; j ++ ) { if ( is_valid ( i , j , size , grid ) ) { return size ; } } } } return 1 ; } public static void Main ( ) { int [ , ] grid = { { 7 , 1 , 4 , 5 , 6 } , { 2 , 5 , 1 , 6 , 4 } , { 1 , 5 , 4 , 3 , 2 } , { 1 , 2 , 7 , 3 , 4 } } ; Console . WriteLine ( largestSquareValidMatrix ( grid ) ) ; } }