human
Maximum size square Sub | Function to find the maximum size of matrix with sum <= K.
N size of rows and M size of cols.
To store the prefix sum of matrix.
Create Prefix Sum.
Traverse each rows.
Update the prefix sum till index i x j.
To store the maximum size of matrix with sum <= K.
Traverse the sum matrix.
Index out of bound.
Maximum possible size of matrix.
Binary Search.
Find middle index.
Check whether sum <= K or not If Yes check for other half of the search.
Else check it in first half.
Update the maximum size matrix.
Print the final answer.
Driver Code.
Given target sum.
Function Call"
Solution in Python:
 Can you provide a code to maximum size square Sub and the other steps required?
assistant
#Here is code to maximum size square Sub and the other steps required.
 def findMaxMatrixSize ( arr , K ) :
	n = len ( arr )
	m = len ( arr [ 0 ] )
	sum = [ [ 0 for i in range ( m + 1 ) ] for j in range ( n + 1 ) ]
	for i in range ( n + 1 ) :
		for j in range ( m + 1 ) :
			if ( i == 0 or j == 0 ) :
				sum [ i ] [ j ] = 0
				continue
			sum [ i ] [ j ] = arr [ i - 1 ] [ j - 1 ] + sum [ i - 1 ] [ j ] + sum [ i ] [ j - 1 ] - sum [ i - 1 ] [ j - 1 ]
	ans = 0
	for i in range ( 1 , n + 1 ) :
		for j in range ( 1 , m + 1 ) :
			if ( i + ans - 1 > n or j + ans - 1 > m ) :
				break
			mid = ans
			lo = ans
			hi = min ( n - i + 1 , m - j + 1 )
			while ( lo < hi ) :
				mid = ( hi + lo + 1 ) // 2
				if ( sum [ i + mid - 1 ] [ j + mid - 1 ] + sum [ i - 1 ] [ j - 1 ] - sum [ i + mid - 1 ] [ j - 1 ] - sum [ i - 1 ] [ j + mid - 1 ] <= K ) :
					lo = mid
				else :
					hi = mid - 1
			ans = max ( ans , lo )
	print ( ans )
if __name__ == ' _ _ main _ _ ' :
	arr = [ [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] , [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] , [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] ]
	K = 4
	findMaxMatrixSize ( arr , K )