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:
-
len(row)is even and in the range of[4, 60]. -
rowis guaranteed to be a permutation of0...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]; } }