Maximum size square Sub | Function to find the maximum size of matrix with sum <= K ; N size of rows and M size of cols ; To store the prefix sum of matrix ; Create Prefix Sum ; Traverse each rows ; Update the prefix sum till index i x j ; To store the maximum size of matrix with sum <= K ; Traverse the sum matrix ; Index out of bound ; Maximum possible size of matrix ; Binary Search ; Find middle index ; Check whether sum <= K or not If Yes check for other half of the search ; Else check it in first half ; Update the maximum size matrix ; Print the final answer ; Driver Code ; Given target sum ; Function Call
function findMaxMatrixSize ( arr , K ) { let i , j ; let n = arr . length ; let m = arr [ 0 ] . length ; let sum = [ ] ; for ( i = 0 ; i < n + 1 ; i ++ ) { sum [ i ] = [ ] ; for ( j = 0 ; j < m + 1 ; j ++ ) { sum [ i ] [ j ] = 0 ; } } for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= m ; j ++ ) { if ( i == 0 j == 0 ) { sum [ i ] [ j ] = 0 ; continue ; } sum [ i ] [ j ] = arr [ i - 1 ] [ j - 1 ] + sum [ i - 1 ] [ j ] + sum [ i ] [ j - 1 ] - sum [ i - 1 ] [ j - 1 ] ; } } let ans = 0 ; for ( i = 1 ; i <= n ; i ++ ) { for ( j = 1 ; j <= m ; j ++ ) { if ( i + ans - 1 > n j + ans - 1 > m ) break ; let mid , lo = ans ; let hi = Math . min ( n - i + 1 , m - j + 1 ) ; while ( lo < hi ) { mid = Math . floor ( ( hi + lo + 1 ) / 2 ) ; if ( sum [ i + mid - 1 ] [ j + mid - 1 ] + sum [ i - 1 ] [ j - 1 ] - sum [ i + mid - 1 ] [ j - 1 ] - sum [ i - 1 ] [ j + mid - 1 ] <= K ) { lo = mid ; } else { hi = mid - 1 ; } } ans = Math . max ( ans , lo ) ; } } document . write ( ans , ' ' ) ; } let arr = [ [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] , [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] , [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] ] ; let K = 4 ; findMaxMatrixSize ( arr , K ) ;