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
def findMaxMatrixSize ( arr , K ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE m = len ( arr [ 0 ] ) NEW_LINE sum = [ [ 0 for i in range ( m + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( m + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT sum [ i ] [ j ] = 0 NEW_LINE continue NEW_LINE DEDENT sum [ i ] [ j ] = arr [ i - 1 ] [ j - 1 ] + sum [ i - 1 ] [ j ] + sum [ i ] [ j - 1 ] - sum [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( i + ans - 1 > n or j + ans - 1 > m ) : NEW_LINE INDENT break NEW_LINE DEDENT mid = ans NEW_LINE lo = ans NEW_LINE hi = min ( n - i + 1 , m - j + 1 ) NEW_LINE while ( lo < hi ) : NEW_LINE INDENT mid = ( hi + lo + 1 ) // 2 NEW_LINE 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 ) : NEW_LINE INDENT lo = mid NEW_LINE DEDENT else : NEW_LINE INDENT hi = mid - 1 NEW_LINE DEDENT DEDENT ans = max ( ans , lo ) NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] , [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] , [ 1 , 1 , 3 , 2 , 4 , 3 , 2 ] ] NEW_LINE K = 4 NEW_LINE findMaxMatrixSize ( arr , K ) NEW_LINE DEDENT