Sponsored
Sponsored
This approach uses a Union-Find (also known as Disjoint Set Union, DSU) data structure to count the number of swaps needed to pair the couples. By treating each couple as a connected component, we can iterate through the row and connect each person to their designated partner. The number of swaps needed is equivalent to the number of components minus one.
Time Complexity: O(N), where N is the number of seats, because each union-find operation is O(1) on average using path compression and union by rank.
Space Complexity: O(N) for the parent array to store the parent of each node.
1class UnionFind {
2 constructor(size) {
3 this.parent = Array.from({ length: size }, (_, i) => i);
4 }
5
6 find(x) {
7 if (this.parent[x] !== x) {
8 this.parent[x] = this.find(this.parent[x]);
9 }
10 return this.parent[x];
11 }
12
13 union(x, y) {
14 const rootX = this.find(x);
15 const rootY = this.find(y);
16 if (rootX !== rootY) {
17 this.parent[rootX] = rootY;
18 }
19 }
20}
21
22function minSwapsCouples(row) {
23 const n = row.length / 2;
24 const uf = new UnionFind(n);
25
26 for (let i = 0; i < row.length; i += 2) {
27 const a = Math.floor(row[i] / 2);
28 const b = Math.floor(row[i + 1] / 2);
29 uf.union(a, b);
30 }
31
32 let swaps = 0;
33 for (let i = 0; i < n; i++) {
34 if (uf.find(i) === i) swaps++;
35 }
36
37 return swaps - 1;
38}
39
40const row = [0, 2, 1, 3];
41console.log(`Minimum swaps required: ${minSwapsCouples(row)}`);In JavaScript, the Union-Find class structures the graph computation for couples. The code evaluates the row array, aggregating each couple through the union function, and finally computes the minimum swaps necessary by traversing the union-find components.
This approach processes the row greedily to minimize swaps by placing each person in its correct position. Misplaced pairs turn into cycles; reducing each cycle requires one swap for each element in excess of two in the cycle. Thus, we can directly count cycles and deduce swaps.
Time Complexity: O(N), iterating the seats for correction.
Space Complexity: O(N), necessary to track positions of individuals.
1#include <iostream>
using namespace std;
int minSwapsCouples(vector<int>& row) {
int n = row.size();
vector<int> pos(n);
for (int i = 0; i < n; ++i) {
pos[row[i]] = i;
}
int swaps = 0;
for (int i = 0; i < n; i += 2) {
int partner = row[i] ^ 1;
if (row[i + 1] != partner) {
++swaps;
int swapWith = pos[partner];
pos[row[i + 1]] = swapWith;
swap(row[i + 1], row[swapWith]);
}
}
return swaps;
}
int main() {
vector<int> row = {0, 2, 1, 3};
cout << "Minimum swaps required: " << minSwapsCouples(row) << endl;
return 0;
}This C++ code utilizes an index mapper and an XOR operation to predict partners, minimizing swaps through navigating and correcting misplacements optimally.