# 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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/765.-couples-holding-hands.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.