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 calculate the largest square with atmost K 1 s for Q queries ; Loop to solve for each query ; Traversing the each sub square and counting total ; Breaks when exceeds the maximum count ; Driver Code
var MAX = 100 ; function largestSquare ( matrix , R , C , q_i , q_j , K , Q ) { for ( var q = 0 ; q < Q ; q ++ ) { var i = q_i [ q ] ; var j = q_j [ q ] ; var min_dist = Math . min ( Math . min ( i , j ) , Math . min ( R - i - 1 , C - j - 1 ) ) ; var ans = - 1 ; for ( var k = 0 ; k <= min_dist ; k ++ ) { var count = 0 ; for ( var row = i - k ; row <= i + k ; row ++ ) for ( var col = j - k ; col <= j + k ; col ++ ) count += matrix [ row ] [ col ] ; if ( count > K ) break ; ans = 2 * k + 1 ; } document . write ( ans + " " ) ; } } var matrix = [ [ 1 , 0 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 , 1 ] , [ 1 , 0 , 0 , 1 , 0 ] ] ; var K = 9 , Q = 1 ; var q_i = [ 1 ] ; var q_j = [ 2 ] ; largestSquare ( matrix , 4 , 5 , q_i , q_j , K , Q ) ;