Largest Square in a Binary Matrix with at most K 1 s for multiple Queries | Python3 implementation to find the largest square in the matrix such that it contains at most 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
MAX = 100 NEW_LINE def largestSquare ( matrix , R , C , q_i , q_j , K , Q ) : NEW_LINE INDENT for q in range ( Q ) : NEW_LINE INDENT i = q_i [ q ] NEW_LINE j = q_j [ q ] NEW_LINE min_dist = min ( min ( i , j ) , min ( R - i - 1 , C - j - 1 ) ) NEW_LINE ans = - 1 NEW_LINE for k in range ( min_dist + 1 ) : NEW_LINE INDENT count = 0 NEW_LINE for row in range ( i - k , i + k + 1 ) : NEW_LINE INDENT for col in range ( j - k , j + k + 1 ) : NEW_LINE INDENT count += matrix [ row ] [ col ] NEW_LINE DEDENT 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