text: Largest Square in a Binary Matrix with at most K 1 s for multiple Queries | 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 ; 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
code: def largestSquare ( matrix , R , C , q_i , q_j , K , Q ) : NEW_LINE INDENT countDP = [ [ 0 for x in range ( C ) ] for x in range ( R ) ] NEW_LINE countDP [ 0 ] [ 0 ] = matrix [ 0 ] [ 0 ] NEW_LINE for i in range ( 1 , R ) : NEW_LINE INDENT countDP [ i ] [ 0 ] = ( countDP [ i - 1 ] [ 0 ] + matrix [ i ] [ 0 ] ) NEW_LINE DEDENT for j in range ( 1 , C ) : NEW_LINE INDENT countDP [ 0 ] [ j ] = ( countDP [ 0 ] [ j - 1 ] + matrix [ 0 ] [ j ] ) NEW_LINE DEDENT for i in range ( 1 , R ) : NEW_LINE INDENT for j in range ( 1 , C ) : NEW_LINE INDENT countDP [ i ] [ j ] = ( matrix [ i ] [ j ] + countDP [ i - 1 ] [ j ] + countDP [ i ] [ j - 1 ] - countDP [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT for q in range ( 0 , Q ) : NEW_LINE INDENT i = q_i [ q ] NEW_LINE j = q_j [ q ] NEW_LINE min_dist = min ( i , j , R - i - 1 , C - j - 1 ) NEW_LINE ans = - 1 NEW_LINE l = 0 NEW_LINE u = min_dist NEW_LINE while ( l <= u ) : NEW_LINE INDENT mid = int ( ( l + u ) / 2 ) NEW_LINE x1 = i - mid NEW_LINE x2 = i + mid NEW_LINE y1 = j - mid NEW_LINE y2 = j + mid NEW_LINE count = countDP [ x2 ] [ y2 ] NEW_LINE if ( x1 > 0 ) : NEW_LINE INDENT count -= countDP [ x1 - 1 ] [ y2 ] NEW_LINE DEDENT if ( y1 > 0 ) : NEW_LINE INDENT count -= countDP [ x2 ] [ y1 - 1 ] NEW_LINE DEDENT if ( x1 > 0 and y1 > 0 ) : NEW_LINE INDENT count += countDP [ x1 - 1 ] [ y1 - 1 ] NEW_LINE DEDENT if ( count <= K ) : NEW_LINE INDENT ans = 2 * mid + 1 NEW_LINE l = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT u = mid - 1 NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT DEDENT matrix = [ [ 1 , 0 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 , 1 ] , [ 1 , 0 , 0 , 1 , 0 ] ] NEW_LINE K = 9 NEW_LINE Q = 1 NEW_LINE q_i = [ 1 ] NEW_LINE q_j = [ 2 ] NEW_LINE largestSquare ( matrix , 4 , 5 , q_i , q_j , K , Q ) NEW_LINE