Count of common subarrays in two different permutations of 1 to N | Python3 implementation of above approach ; Initialising Map for Index Mapping ; Mapping elements of A ; Modify elements of B according to Map ; Changing B [ i ] as the index of B [ i ] in A ; Count of common subarrays ; Traversing array B ; While consecutive elements are found , we increment K ; Add number of subarrays with length K to total count ; Driver code
def commonSubarrays ( A , B , N ) : NEW_LINE INDENT Map = [ 0 for i in range ( N + 1 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT Map [ A [ i ] ] = i NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT B [ i ] = Map [ B [ i ] ] NEW_LINE DEDENT count = 0 NEW_LINE i = 0 NEW_LINE while i < N : NEW_LINE INDENT K = 1 NEW_LINE i += 1 NEW_LINE while i < N and B [ i ] == B [ i - 1 ] + 1 : NEW_LINE INDENT i += 1 NEW_LINE K += 1 NEW_LINE DEDENT count = count + ( ( K ) * ( K + 1 ) ) // 2 NEW_LINE DEDENT return count NEW_LINE DEDENT N = 3 NEW_LINE A = [ 1 , 2 , 3 ] NEW_LINE B = [ 2 , 3 , 1 ] NEW_LINE print ( commonSubarrays ( A , B , N ) ) NEW_LINE N = 5 NEW_LINE A = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE B = [ 2 , 3 , 1 , 4 , 5 ] NEW_LINE print ( commonSubarrays ( A , B , N ) ) NEW_LINE