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 find the largest square in the matrix such that it contains atmost K 1 's  ; Precomputation of the countDP prefix sum of the matrix ; Loop to solve each query ; Binary Search to the side which have atmost in K 1 's in square  ; Count total number of 1 s in the sub square considered ; If the count is less than or equals to the maximum move to right half ; Driver code
import java . util . * ; class GFG { static void largestSquare ( int matrix [ ] [ ] , int R , int C , int q_i [ ] , int q_j [ ] , int K , int Q ) { int countDP [ ] [ ] = new int [ R ] [ C ] ; for ( int i = 0 ; i < R ; i ++ ) for ( int j = 0 ; j < C ; j ++ ) countDP [ i ] [ j ] = 0 ; countDP [ 0 ] [ 0 ] = matrix [ 0 ] [ 0 ] ; for ( int i = 1 ; i < R ; i ++ ) countDP [ i ] [ 0 ] = countDP [ i - 1 ] [ 0 ] + matrix [ i ] [ 0 ] ; for ( int j = 1 ; j < C ; j ++ ) countDP [ 0 ] [ j ] = countDP [ 0 ] [ j - 1 ] + matrix [ 0 ] [ j ] ; for ( int i = 1 ; i < R ; i ++ ) for ( int 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 ( 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 , l = 0 , u = min_dist ; while ( l <= u ) { int mid = ( l + u ) / 2 ; int x1 = i - mid , x2 = i + mid ; int y1 = j - mid , y2 = j + mid ; int 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 ) { ans = 2 * mid + 1 ; l = mid + 1 ; } else u = mid - 1 ; } System . out . println ( ans ) ; } } 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 ) ; } }