Find Maximum Length Of A Square Submatrix Having Sum Of Elements At | Function to return maximum length of square submatrix having sum of elements at - most K ; Matrix to store prefix sum ; Current maximum length ; Variable for storing maximum length of square ; Calculating prefix sum ; Checking whether there exits square with length cur_max + 1 or not ; Returning the maximum length ; Driver code
function maxLengthSquare ( row , column , arr , k ) { let sum = new Array ( ) ; [ row + 1 ] [ column + 1 ] ; for ( let i = 0 ; i < row + 1 ; i ++ ) { let temp = new Array ( ) ; for ( let j = 0 ; j < column + 1 ; j ++ ) { temp . push ( [ ] ) } sum . push ( temp ) } for ( let i = 1 ; i <= row ; i ++ ) for ( let j = 0 ; j <= column ; j ++ ) sum [ i ] [ j ] = 0 ; let cur_max = 1 ; let max = 0 ; for ( let i = 1 ; i <= row ; i ++ ) { for ( let j = 1 ; j <= column ; j ++ ) { sum [ i ] [ j ] = sum [ i - 1 ] [ j ] + sum [ i ] [ j - 1 ] + arr [ i - 1 ] [ j - 1 ] - sum [ i - 1 ] [ j - 1 ] ; if ( i >= cur_max && j >= cur_max && sum [ i ] [ j ] - sum [ i - cur_max ] [ j ] - sum [ i ] [ j - cur_max ] + sum [ i - cur_max ] [ j - cur_max ] <= k ) { max = cur_max ++ ; } } } return max ; } let row = 4 , column = 4 ; let matrix = [ [ 1 , 1 , 1 , 1 ] , [ 1 , 0 , 0 , 0 ] , [ 1 , 0 , 0 , 0 ] , [ 1 , 0 , 0 , 0 ] ] ; let k = 6 ; let ans = maxLengthSquare ( row , column , matrix , k ) ; document . write ( ans ) ;