> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/765.-couples-holding-hands.md).

# 765. Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing **any** two people, then they stand up and switch seats.

The people and seats are represented by an integer from `0` to `2N-1`, the couples are numbered in order, the first couple being `(0, 1)`, the second couple being `(2, 3)`, and so on with the last couple being `(2N-2, 2N-1)`.

The couples' initial seating is given by `row[i]` being the value of the person who is initially sitting in the i-th seat.

**Example 1:**<br>

```
Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
```

**Example 2:**<br>

```
Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
```

**Note:**

1. `len(row)` is even and in the range of `[4, 60]`.
2. `row` is guaranteed to be a permutation of `0...len(row)-1`.

{% hint style="info" %}
利用數字間的XOR找到該在一起的pair，例如0^0x1之後是1，1＾0x1之後是0，所以0和1是一組。和0x1做XOR可以把奇偶數互換。
{% endhint %}

```cpp
// Greedy
int minSwapsCouples(vector<int>& row) { // time: O(n^2); space: O(1)
    int res = 0, n = row.size();
    for (int i = 0; i < n - 1; i += 2) {
        if (row[i + 1] == (row[i] ^ 1)) continue;
        ++res;
        for (int j = i + 1; j < n; ++j) {
            if (row[j] == (row[i] ^ 1)) {
                swap(row[i + 1], row[j]);
                break;
            }
        }
    }
    return res;
}
```

{% hint style="info" %}
原本有獨立的n/2個group，每遇到一個root值不相等的兩個數，就把他們之間連結起來，代表需要這兩個數的group有需要swap，一開始cnt設為n/2，代表有多少個連結起來的group，最後再用n/2減去這個數量就是需要做的交換次數。
{% endhint %}

```cpp
// Union Find
int find(vector<int>& root, int i) {
    return (i == root[i]) ? i : root[i] = find(root, root[i]);
}
int minSwapsCouples(vector<int>& row) { // time: O(log*(n)); space: O(n)
    int res = 0, n = row.size(), cnt = n / 2;
    vector<int> root(cnt, 0);
    for (int i = 0; i < cnt; ++i) root[i] = i;
    for (int i = 0; i < n - 1; i += 2) {
        int x = find(root, row[i] / 2);
        int y = find(root, row[i + 1] / 2);
        if (x != y) {
            root[x] = y;
            --cnt;
        }
    }
    return n / 2 - cnt;
}
```

{% hint style="info" %}
概念上類似Union Find，但這個解法是用hashmap來實現。
{% endhint %}

```cpp
// Similar Union Find by Hashmap
void helper(unordered_map<int, int>& m, int x, int y) {
    int c1 = min(x, y), c2 = max(x, y);
    if (c1 == c2) return;
    if (m.count(c1)) helper(m, m[c1], c2);
    else m[c1] = c2;
}
int minSwapsCouples(vector<int>& row) { // time: O(n); space: O(n)
    unordered_map<int, int> m;
    for (int i = 0; i < row.size(); i += 2) {
        helper(m, row[i] / 2, row[i + 1] / 2);
    }
    return m.size();
}
```

```cpp
int minSwapsCouples(vector<int>& row) { // time: O(n); space: O(n)
    int res = 0, n = row.size();
    vector<int> ptn(n, 0), pos(n, 0);
    for (int i = 0; i < n; ++i) {
        ptn[i] = i % 2 == 0 ? i + 1 : i - 1;
        pos[row[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = ptn[pos[ptn[row[i]]]]; j != i; j = ptn[pos[ptn[row[i]]]]) {
            swap(row[i], row[j]);
            swap(pos[row[i]], pos[row[j]]);
            ++res;
        }
    }
    return res;
}
```