Number of ways to select equal sized subarrays from two arrays having atleast K equal pairs of elements | 2D prefix sum for submatrix sum query for matrix ; Function to find the prefix sum of the matrix from i and j ; Function to count the number of ways to select equal sized subarrays such that they have atleast K common elements ; Combining the two arrays ; Calculating the 2D prefix sum ; iterating through all the elements of matrix and considering them to be the bottom right ; applying binary search over side length ; if sum of this submatrix >= k then new search space will be [ low , mid ] ; else new search space will be [ mid + 1 , high ] ; Adding the total submatrices ; Driver Code
prefix_2D = [ [ 0 for x in range ( 2005 ) ] for y in range ( 2005 ) ] NEW_LINE def subMatrixSum ( i , j , length ) : NEW_LINE INDENT return ( prefix_2D [ i ] [ j ] - prefix_2D [ i ] [ j - length ] - prefix_2D [ i - length ] [ j ] + prefix_2D [ i - length ] [ j - length ] ) NEW_LINE DEDENT def numberOfWays ( a , b , n , m , k ) : NEW_LINE INDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( a [ i - 1 ] == b [ j - 1 ] ) : NEW_LINE INDENT prefix_2D [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT prefix_2D [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT prefix_2D [ i ] [ j ] += prefix_2D [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT prefix_2D [ i ] [ j ] += prefix_2D [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT answer = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT low = 1 NEW_LINE high = min ( i , j ) NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = ( low + high ) >> 1 NEW_LINE if ( subMatrixSum ( i , j , mid ) >= k ) : NEW_LINE INDENT high = mid NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT if ( subMatrixSum ( i , j , low ) >= k ) : NEW_LINE INDENT answer += ( min ( i , j ) - low + 1 ) NEW_LINE DEDENT DEDENT DEDENT return answer NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 2 NEW_LINE M = 3 NEW_LINE A = [ 1 , 2 ] NEW_LINE B = [ 1 , 2 , 3 ] NEW_LINE K = 1 NEW_LINE print ( numberOfWays ( A , B , N , M , K ) ) NEW_LINE DEDENT