Maximum size of square such that all submatrices of that size have sum less than K | Size of matrix ; Function to preprocess the matrix for computing the sum of every possible matrix of the given size ; Loop to copy the first row of the matrix into the aux matrix ; Computing the sum column - wise ; Computing row wise sum ; Function to find the sum of a submatrix with the given indices ; Overall sum from the top to right corner of matrix ; Removing the sum from the top corer of the matrix ; Remove the overlapping sum ; Add the sum of top corner which is subtracted twice ; Function to check whether square sub matrices of size mid satisfy the condition or not ; Iterating throught all possible submatrices of given size ; Function to find the maximum square size possible with the such that every submatrix have sum less than the given sum ; Search space ; Binary search for size ; Check if the mid satisfies the given condition ; Driver Code
let N = 4 ; let M = 5 ; function preProcess ( mat , aux ) { for ( let i = 0 ; i < M ; i ++ ) aux [ 0 ] [ i ] = mat [ 0 ] [ i ] ; for ( let i = 1 ; i < N ; i ++ ) for ( let j = 0 ; j < M ; j ++ ) aux [ i ] [ j ] = mat [ i ] [ j ] + aux [ i - 1 ] [ j ] ; for ( let i = 0 ; i < N ; i ++ ) for ( let j = 1 ; j < M ; j ++ ) aux [ i ] [ j ] += aux [ i ] [ j - 1 ] ; } function sumQuery ( aux , tli , tlj , rbi , rbj ) { let res = aux [ rbi ] [ rbj ] ; if ( tli > 0 ) res = res - aux [ tli - 1 ] [ rbj ] ; if ( tlj > 0 ) res = res - aux [ rbi ] [ tlj - 1 ] ; if ( tli > 0 && tlj > 0 ) res = res + aux [ tli - 1 ] [ tlj - 1 ] ; return res ; } function check ( mid , aux , K ) { let satisfies = true ; for ( let x = 0 ; x < N ; x ++ ) { for ( let y = 0 ; y < M ; y ++ ) { if ( x + mid - 1 <= N - 1 && y + mid - 1 <= M - 1 ) { if ( sumQuery ( aux , x , y , x + mid - 1 , y + mid - 1 ) > K ) satisfies = false ; } } } return ( satisfies == true ) ; } function maximumSquareSize ( mat , K ) { let aux = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { aux [ i ] = new Array ( M ) ; } preProcess ( mat , aux ) ; let low = 1 , high = Math . min ( N , M ) ; let mid ; while ( high - low > 1 ) { mid = Math . floor ( ( low + high ) / 2 ) ; if ( check ( mid , aux , K ) ) { low = mid ; } else high = mid ; } if ( check ( high , aux , K ) ) return high ; return low ; } let K = 30 ; let mat = [ [ 1 , 2 , 3 , 4 , 6 ] , [ 5 , 3 , 8 , 1 , 2 ] , [ 4 , 6 , 7 , 5 , 5 ] , [ 2 , 4 , 8 , 9 , 4 ] ] ; document . write ( maximumSquareSize ( mat , K ) ) ;