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 ; Calculating the number of 1 s in the submatrix ; Driver 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 for k in range ( 0 , min_dist + 1 ) : NEW_LINE INDENT x1 = i - k NEW_LINE x2 = i + k NEW_LINE y1 = j - k NEW_LINE y2 = j + k 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 break NEW_LINE DEDENT ans = 2 * k + 1 NEW_LINE 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