Maximum size of square such that all submatrices of that size have sum less than K | Size of matrix ; 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 find the maximum square size possible with the such that every submatrix have sum less than the given sum ; Loop to choose the size of matrix ; Loop to find the sum of the matrix of every possible submatrix ; Driver Code
N = 4 NEW_LINE M = 5 NEW_LINE def preProcess ( mat , aux ) : NEW_LINE INDENT for i in range ( M ) : NEW_LINE INDENT aux [ 0 ] [ i ] = mat [ 0 ] [ i ] NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT aux [ i ] [ j ] = ( mat [ i ] [ j ] + aux [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( 1 , M ) : NEW_LINE INDENT aux [ i ] [ j ] += aux [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT 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 maximumSquareSize ( mat , K ) : NEW_LINE INDENT aux = [ [ 0 for x in range ( M ) ] for y in range ( N ) ] NEW_LINE preProcess ( mat , aux ) NEW_LINE for i in range ( min ( N , M ) , 0 , - 1 ) : NEW_LINE INDENT satisfies = True NEW_LINE for x in range ( N ) : NEW_LINE INDENT for y in range ( M ) : NEW_LINE INDENT if ( x + i - 1 <= N - 1 and y + i - 1 <= M - 1 ) : NEW_LINE INDENT if ( sumQuery ( aux , x , y , x + i - 1 , y + i - 1 ) > K ) : NEW_LINE INDENT satisfies = False NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( satisfies == True ) : NEW_LINE INDENT return ( i ) NEW_LINE DEDENT DEDENT return 0 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