##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/765.html

# 765. Couples Holding Hands (Hard)

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:

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:

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.

Related Topics:
Greedy, Union Find, Graph

Similar Questions:

## Solution 1. Union Find

// OJ: https://leetcode.com/problems/couples-holding-hands/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/couples-holding-hands/discuss/117520/Java-union-find-easy-to-understand-5-ms
class UnionFind {
vector<int> id, rank;
int cnt;
public:
UnionFind(int n) : id(n), rank(n, 1), cnt(n) {
for(int i = 0; i < n; ++i) id[i] = i;
}
void connect(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return;
if (rank[x] <= rank[y]) {
id[x] = y;
if (rank[x] == rank[y]) rank[y]++;
} else id[y] = x;
--cnt;
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
int getCount() { return cnt; }
};
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int N = row.size() / 2;
UnionFind uf(N);
for (int i = 0; i < N; ++i) uf.connect(row[2 * i] / 2, row[2 * i + 1] / 2);
return N - uf.getCount();
}
};

• class Solution {
public int minSwapsCouples(int[] row) {
int swaps = 0;
Map<Integer, Integer> numberIndexMap = new HashMap<Integer, Integer>();
int length = row.length;
for (int i = 0; i < length; i++)
numberIndexMap.put(row[i], i);
for (int i = 0; i < length; i += 2) {
int num1 = row[i];
int couple = getCouple(num1);
int coupleIndex = numberIndexMap.get(couple);
if (coupleIndex != i + 1) {
int num2 = row[i + 1];
row[i + 1] = couple;
row[coupleIndex] = num2;
numberIndexMap.put(couple, i + 1);
numberIndexMap.put(num2, coupleIndex);
swaps++;
}
}
return swaps;
}

public int getCouple(int num) {
return num % 2 == 0 ? num + 1 : num - 1;
}
}

############

class Solution {
private int[] p;

public int minSwapsCouples(int[] row) {
int n = row.length >> 1;
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (int i = 0; i < row.length; i += 2) {
int a = row[i] >> 1, b = row[i + 1] >> 1;
p[find(a)] = find(b);
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (i == find(i)) {
++cnt;
}
}
return n - cnt;
}

private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}

• // OJ: https://leetcode.com/problems/couples-holding-hands/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/couples-holding-hands/discuss/117520/Java-union-find-easy-to-understand-5-ms
class UnionFind {
vector<int> id, rank;
int cnt;
public:
UnionFind(int n) : id(n), rank(n, 1), cnt(n) {
for(int i = 0; i < n; ++i) id[i] = i;
}
void connect(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return;
if (rank[x] <= rank[y]) {
id[x] = y;
if (rank[x] == rank[y]) rank[y]++;
} else id[y] = x;
--cnt;
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
int getCount() { return cnt; }
};
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int N = row.size() / 2;
UnionFind uf(N);
for (int i = 0; i < N; ++i) uf.connect(row[2 * i] / 2, row[2 * i + 1] / 2);
return N - uf.getCount();
}
};

• class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]

n = len(row) >> 1
p = list(range(n))
for i in range(0, len(row), 2):
a, b = row[i] >> 1, row[i + 1] >> 1
p[find(a)] = find(b)
return n - sum(i == find(i) for i in range(n))

############

class Solution(object):
def minSwapsCouples(self, row):
"""
:type row: List[int]
:rtype: int
"""
res = 0
n = len(row)
for i in range(0, n - 1, 2):
if row[i + 1] == (row[i] ^ 1):
continue
for j in range(i + 1, n):
if row[j] == (row[i] ^ 1):
row[j], row[i + 1] = row[i + 1], row[j]
res += 1
return res

• var p []int

func minSwapsCouples(row []int) int {
n := len(row) >> 1
p = make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
}
for i := 0; i < len(row); i += 2 {
a, b := row[i]>>1, row[i+1]>>1
p[find(a)] = find(b)
}
cnt := 0
for i := 0; i < n; i++ {
if i == find(i) {
cnt++
}
}
return n - cnt
}

func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}

• function minSwapsCouples(row: number[]): number {
const n = row.length >> 1;
const p: number[] = Array(n)
.fill(0)
.map((_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
for (let i = 0; i < n << 1; i += 2) {
const a = row[i] >> 1;
const b = row[i + 1] >> 1;
p[find(a)] = find(b);
}
let ans = n;
for (let i = 0; i < n; ++i) {
if (i === find(i)) {
--ans;
}
}
return ans;
}


• public class Solution {
private int[] p;

public int MinSwapsCouples(int[] row) {
int n = row.Length >> 1;
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (int i = 0; i < n << 1; i += 2) {
int a = row[i] >> 1;
int b = row[i + 1] >> 1;
p[find(a)] = find(b);
}
int ans = n;
for (int i = 0; i < n; ++i) {
if (p[i] == i) {
--ans;
}
}
return ans;
}

private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}