Count of submatrix with sum X in a given Matrix | Size of a column ; Function to find the count of submatrix whose sum is X ; Copying arr to dp and making it indexed 1 ; Precalculate and store the sum of all rectangles with upper left corner at ( 0 , 0 ) ; ; Calculating sum in a 2d grid ; Stores the answer ; Minimum length of square ; Maximum length of square ; Flag to set if sub - square with sum X is found ; Calculate lower right index if upper right corner is at { i , j } ; Calculate the sum of elements in the submatrix with upper left column { i , j } and lower right column at { ni , nj } ; ; If sum X is found ; If sum > X , then size of the square with sum X must be less than mid ; If sum < X , then size of the square with sum X must be greater than mid ; If found , increment count by 1 ; ; Driver Code ; Given matrix arr [ ] [ ] ; Function call
m = 5 NEW_LINE def countSubsquare ( arr , n , X ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( m + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT dp [ i + 1 ] [ j + 1 ] = arr [ i ] [ j ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] += ( dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ] - dp [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT cnt = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT lo = 1 NEW_LINE hi = min ( n - i , m - j ) + 1 NEW_LINE found = False NEW_LINE while ( lo <= hi ) : NEW_LINE INDENT mid = ( lo + hi ) // 2 NEW_LINE ni = i + mid - 1 NEW_LINE nj = j + mid - 1 NEW_LINE sum = ( dp [ ni ] [ nj ] - dp [ ni ] [ j - 1 ] - dp [ i - 1 ] [ nj ] + dp [ i - 1 ] [ j - 1 ] ) NEW_LINE if ( sum >= X ) : NEW_LINE INDENT if ( sum == X ) : NEW_LINE INDENT found = True NEW_LINE DEDENT hi = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT lo = mid + 1 NEW_LINE DEDENT DEDENT if ( found == True ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT DEDENT return cnt NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N , X = 4 , 10 NEW_LINE arr = [ [ 2 , 4 , 3 , 2 , 10 ] , [ 3 , 1 , 1 , 1 , 5 ] , [ 1 , 1 , 2 , 1 , 4 ] , [ 2 , 1 , 1 , 1 , 3 ] ] NEW_LINE print ( countSubsquare ( arr , N , X ) ) NEW_LINE DEDENT