Minimum number of swaps required for arranging pairs adjacent to each other

There are A pairs and therefore 2A people. Each person has a unique number ranging from 1 to 2A.
An array of integers B shows the arrangement of these 2N people.

A matrix C of size N x 2 is given describing pairs i.e. people that are partner of each other.
C[i][0] and C[i][1] are partner of each other.

Find the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other.



Input Format

The First argument given is an integer A.
The Second argument given is the integer array B.
The Third argument given is matrix C.

Output Format

Return the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other

Constraints

1 <= A <= 20
1 <= B[i] <= 2*A
C[i][0]!=C[i][1]
1 <= C[i][0], C[i][1] <= 2*A

For Example

Input 1:
    A = 3
    B = [3, 5, 6, 4, 1, 2]
    C = [   [1, 3]
            [2, 6]
            [4, 5]  ]
Output 1:
    2
    Explanation 1:
        One of the ways to arraange them 
        1. swap(5 and 6) order becomes : [3, 6, 5, 4, 1, 2]
        2. swap(6 and 1) order becomes:  [3, 1, 5, 4, 6, 2]
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Minimum number of swaps required for arranging pairs adjacent to each other on Interview Code Editor
Sign Up
to access hints and editorial solutions for Minimum number of swaps required for arranging pairs adjacent to each other

Discussion


Loading...
Click here to start solving coding interview questions