Largest Square in a Binary Matrix with at most K 1 s for multiple Queries | Javascript implementation to find the largest square in the matrix such that it contains atmost K 1 's ; Function to find the largest square in the matrix such that it contains atmost K 1 's ; Precomputing the countDP prefix sum of the matrix ; Loop to solve Queries ; Calculating the maximum possible distance of the centre from edge ; Calculating the number of 1 s in the submatrix ; Driver Code
let MAX = 100 ; function largestSquare ( matrix , R , C , q_i , q_j , K , Q ) { let countDP = new Array ( R ) ; for ( let i = 0 ; i < R ; i ++ ) { countDP [ i ] = new Array ( C ) ; for ( let j = 0 ; j < C ; j ++ ) countDP [ i ] [ j ] = 0 ; } countDP [ 0 ] [ 0 ] = matrix [ 0 ] [ 0 ] ; for ( let i = 1 ; i < R ; i ++ ) countDP [ i ] [ 0 ] = countDP [ i - 1 ] [ 0 ] + matrix [ i ] [ 0 ] ; for ( let j = 1 ; j < C ; j ++ ) countDP [ 0 ] [ j ] = countDP [ 0 ] [ j - 1 ] + matrix [ 0 ] [ j ] ; for ( let i = 1 ; i < R ; i ++ ) for ( let j = 1 ; j < C ; j ++ ) countDP [ i ] [ j ] = matrix [ i ] [ j ] + countDP [ i - 1 ] [ j ] + countDP [ i ] [ j - 1 ] - countDP [ i - 1 ] [ j - 1 ] ; for ( let q = 0 ; q < Q ; q ++ ) { let i = q_i [ q ] ; let j = q_j [ q ] ; let min_dist = Math . min ( Math . min ( i , j ) , Math . min ( R - i - 1 , C - j - 1 ) ) ; let ans = - 1 ; for ( let k = 0 ; k <= min_dist ; k ++ ) { let x1 = i - k , x2 = i + k ; let y1 = j - k , y2 = j + k ; let count = countDP [ x2 ] [ y2 ] ; if ( x1 > 0 ) count -= countDP [ x1 - 1 ] [ y2 ] ; if ( y1 > 0 ) count -= countDP [ x2 ] [ y1 - 1 ] ; if ( x1 > 0 && y1 > 0 ) count += countDP [ x1 - 1 ] [ y1 - 1 ] ; if ( count > K ) break ; ans = 2 * k + 1 ; } document . write ( ans + " " ) ; } } let matrix = [ [ 1 , 0 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 , 1 ] , [ 1 , 0 , 0 , 1 , 0 ] ] ; let K = 9 , Q = 1 ; let q_i = [ 1 ] ; let q_j = [ 2 ] ; largestSquare ( matrix , 4 , 5 , q_i , q_j , K , Q ) ;