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.
1import java.util.*;
2
3class Solution {
4 static class UnionFind {
5 int[] parent;
6
7 UnionFind(int n) {
8 parent = new int[n];
9 for (int i = 0; i < n; i++) {
10 parent[i] = i;
11 }
12 }
13
14 int find(int x) {
15 if (parent[x] != x) {
16 parent[x] = find(parent[x]);
17 }
18 return parent[x];
19 }
20
21 void union(int x, int y) {
22 int rootX = find(x);
23 int rootY = find(y);
24 if (rootX != rootY) {
25 parent[rootX] = rootY;
26 }
27 }
28 }
29
30 public int minSwapsCouples(int[] row) {
31 int n = row.length / 2;
32 UnionFind uf = new UnionFind(n);
33 for (int i = 0; i < row.length; i += 2) {
34 int a = row[i];
35 int b = row[i + 1];
36 uf.union(a / 2, b / 2);
37 }
38
39 int swaps = 0;
40 for (int i = 0; i < n; i++) {
41 if (uf.find(i) == i) swaps++;
42 }
43 return swaps - 1;
44 }
45
46 public static void main(String[] args) {
47 Solution sol = new Solution();
48 int[] row = {0, 2, 1, 3};
49 System.out.println("Minimum swaps required: " + sol.minSwapsCouples(row));
50 }
51}The Java implementation uses the Union-Find data structure to unite couples. The function then calculates the minimum swaps required by checking the number of distinct components formed, using the number of components to formulate the swaps needed.
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.
1using System.Collections.Generic;
public class Solution {
public int MinSwapsCouples(int[] row) {
int n = row.Length;
int[] pos = new int[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;
int temp = row[i + 1];
row[i + 1] = row[swapWith];
row[swapWith] = temp;
}
}
return swaps;
}
public static void Main(string[] args) {
int[] row = {0, 2, 1, 3};
Solution sol = new Solution();
Console.WriteLine("Minimum swaps required: " + sol.MinSwapsCouples(row));
}
}This C# solution iterates over the row, evaluating partner relationships through mathematical partners indices, and reorders using direct swaps, delivering a correct number of operations needed.