human
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"
Solution in Python:
assistant
#Here is code to maximum size of square such that all submatrices of that size have sum less than K and the other steps required.
 def preProcess ( mat , aux ) :
	for i in range ( 5 ) :
		aux [ 0 ] [ i ] = mat [ 0 ] [ i ]
	for i in range ( 1 , 4 ) :
		for j in range ( 5 ) :
			aux [ i ] [ j ] = ( mat [ i ] [ j ] + aux [ i - 1 ] [ j ] )
	for i in range ( 4 ) :
		for j in range ( 1 , 5 ) :
			aux [ i ] [ j ] += aux [ i ] [ j - 1 ]
	return aux
def sumQuery ( aux , tli , tlj , rbi , rbj ) :
	res = aux [ rbi ] [ rbj ]
	if ( tli > 0 ) :
		res = res - aux [ tli - 1 ] [ rbj ]
	if ( tlj > 0 ) :
		res = res - aux [ rbi ] [ tlj - 1 ]
	if ( tli > 0 and tlj > 0 ) :
		res = res + aux [ tli - 1 ] [ tlj - 1 ]
	return res
def check ( mid , aux , K ) :
	satisfies = True
	for x in range ( 4 ) :
		for y in range ( 5 ) :
			if ( x + mid - 1 <= 4 - 1 and y + mid - 1 <= 5 - 1 ) :
				if ( sumQuery ( aux , x , y , x + mid - 1 , y + mid - 1 ) > K ) :
					satisfies = False
	return True if satisfies == True else False
def maximumSquareSize ( mat , K ) :
	aux = [ [ 0 for i in range ( 5 ) ] for i in range ( 4 ) ]
	aux = preProcess ( mat , aux )
	low , high = 1 , min ( 4 , 5 )
	mid = 0
	while ( high - low > 1 ) :
		mid = ( low + high ) // 2
		if ( check ( mid , aux , K ) ) :
			low = mid
		else :
			high = mid
	if ( check ( high , aux , K ) ) :
		return high
	return low
if __name__ == ' _ _ main _ _ ' :
	K = 30
	mat = [ [ 1 , 2 , 3 , 4 , 6 ] , [ 5 , 3 , 8 , 1 , 2 ] , [ 4 , 6 , 7 , 5 , 5 ] , [ 2 , 4 , 8 , 9 , 4 ] ]
	print ( maximumSquareSize ( mat , K ) )