Maximum size of square such that all submatrices of that size have sum less than K | Function to preprocess the matrix for computing the sum of every possible matrix of the given size ; Loop to copy the first row of the matrix into the aux matrix ; Computing the sum column - wise ; Computing row wise sum ; Function to find the sum of a submatrix with the given indices ; Overall sum from the top to right corner of matrix ; Removing the sum from the top corer of the matrix ; Remove the overlapping sum ; Add the sum of top corner which is subtracted twice ; Function to check whether square sub matrices of size mid satisfy the condition or not ; Iterating throught all possible submatrices of given size ; Function to find the maximum square size possible with the such that every submatrix have sum less than the given sum ; Search space ; Binary search for size ; Check if the mid satisfies the given condition ; Driver Code
def preProcess ( mat , aux ) : NEW_LINE INDENT for i in range ( 5 ) : NEW_LINE INDENT aux [ 0 ] [ i ] = mat [ 0 ] [ i ] NEW_LINE DEDENT for i in range ( 1 , 4 ) : NEW_LINE INDENT for j in range ( 5 ) : NEW_LINE INDENT aux [ i ] [ j ] = ( mat [ i ] [ j ] + aux [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT for i in range ( 4 ) : NEW_LINE INDENT for j in range ( 1 , 5 ) : NEW_LINE INDENT aux [ i ] [ j ] += aux [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT return aux NEW_LINE DEDENT def sumQuery ( aux , tli , tlj , rbi , rbj ) : NEW_LINE INDENT res = aux [ rbi ] [ rbj ] NEW_LINE if ( tli > 0 ) : NEW_LINE INDENT res = res - aux [ tli - 1 ] [ rbj ] NEW_LINE DEDENT if ( tlj > 0 ) : NEW_LINE INDENT res = res - aux [ rbi ] [ tlj - 1 ] NEW_LINE DEDENT if ( tli > 0 and tlj > 0 ) : NEW_LINE INDENT res = res + aux [ tli - 1 ] [ tlj - 1 ] NEW_LINE DEDENT return res NEW_LINE DEDENT def check ( mid , aux , K ) : NEW_LINE INDENT satisfies = True NEW_LINE for x in range ( 4 ) : NEW_LINE INDENT for y in range ( 5 ) : NEW_LINE INDENT if ( x + mid - 1 <= 4 - 1 and y + mid - 1 <= 5 - 1 ) : NEW_LINE INDENT if ( sumQuery ( aux , x , y , x + mid - 1 , y + mid - 1 ) > K ) : NEW_LINE INDENT satisfies = False NEW_LINE DEDENT DEDENT DEDENT DEDENT return True if satisfies == True else False NEW_LINE DEDENT def maximumSquareSize ( mat , K ) : NEW_LINE INDENT aux = [ [ 0 for i in range ( 5 ) ] for i in range ( 4 ) ] NEW_LINE aux = preProcess ( mat , aux ) NEW_LINE low , high = 1 , min ( 4 , 5 ) NEW_LINE mid = 0 NEW_LINE while ( high - low > 1 ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( check ( mid , aux , K ) ) : NEW_LINE INDENT low = mid NEW_LINE DEDENT else : NEW_LINE INDENT high = mid NEW_LINE DEDENT DEDENT if ( check ( high , aux , K ) ) : NEW_LINE INDENT return high NEW_LINE DEDENT return low NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT K = 30 NEW_LINE mat = [ [ 1 , 2 , 3 , 4 , 6 ] , [ 5 , 3 , 8 , 1 , 2 ] , [ 4 , 6 , 7 , 5 , 5 ] , [ 2 , 4 , 8 , 9 , 4 ] ] NEW_LINE print ( maximumSquareSize ( mat , K ) ) NEW_LINE DEDENT