Largest Square in a Binary Matrix with at most K 1 s for multiple Queries | Java 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
class GFG { static int MAX = 100 ; static void largestSquare ( int matrix [ ] [ ] , int R , int C , int q_i [ ] , int q_j [ ] , int K , int Q ) { for ( int q = 0 ; q < Q ; q ++ ) { int i = q_i [ q ] ; int j = q_j [ q ] ; int min_dist = Math . min ( Math . min ( i , j ) , Math . min ( R - i - 1 , C - j - 1 ) ) ; int ans = - 1 ; for ( int k = 0 ; k <= min_dist ; k ++ ) { int count = 0 ; for ( int row = i - k ; row <= i + k ; row ++ ) for ( int col = j - k ; col <= j + k ; col ++ ) count += matrix [ row ] [ col ] ; if ( count > K ) break ; ans = 2 * k + 1 ; } System . out . print ( ans + "NEW_LINE"); } } public static void main ( String [ ] args ) { int matrix [ ] [ ] = { { 1 , 0 , 1 , 0 , 0 } , { 1 , 0 , 1 , 1 , 1 } , { 1 , 1 , 1 , 1 , 1 } , { 1 , 0 , 0 , 1 , 0 } } ; int K = 9 , Q = 1 ; int q_i [ ] = { 1 } ; int q_j [ ] = { 2 } ; largestSquare ( matrix , 4 , 5 , q_i , q_j , K , Q ) ; } }