There are n couples sitting in 2n seats arranged in a row and want to hold hands.
The people and seats are represented by an integer array row where row[i]
is the ID of the person sitting in the ith seat. 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).
Return 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 key idea is to greedily swap people so that each couple sits together. For each seat pair, if the person sitting next to the current person is not their partner, swap them with the partner. Using a position map allows us to find and swap efficiently.
classSolution {
public: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 ans =0;
for (int i =0; i < n; i +=2) {
int x = row[i];
int y = x ^1;
if (row[i+1] != y) {
int j = pos[y];
swap(row[i+1], row[j]);
pos[row[j]] = j;
pos[row[i+1]] = i+1;
++ans;
}
}
return ans;
}
};
classSolution {
publicintminSwapsCouples(int[] row) {
int n = row.length;
int[] pos =newint[n];
for (int i = 0; i < n; i++) pos[row[i]]= i;
int ans = 0;
for (int i = 0; i < n; i += 2) {
int x = row[i];
int y = x ^ 1;
if (row[i+1]!= y) {
int j = pos[y];
int tmp = row[i+1];
row[i+1]= row[j];
row[j]= tmp;
pos[row[j]]= j;
pos[row[i+1]]= i+1;
ans++;
}
}
return ans;
}
}
classSolution {
funminSwapsCouples(row: IntArray): Int {
val n = row.size
val pos = IntArray(n)
for (i in0 until n) pos[row[i]] = i
var ans = 0var i = 0while (i < n) {
val x = row[i]
val y = x xor 1if (row[i+1] != y) {
val j = pos[y]
val tmp = row[i+1]
row[i+1] = row[j]
row[j] = tmp
pos[row[j]] = j
pos[row[i+1]] = i+1 ans++ }
i +=2 }
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution:
defminSwapsCouples(self, row: list[int]) -> int:
n = len(row)
pos = [0] * n
for i, v in enumerate(row):
pos[v] = i
ans =0for i in range(0, n, 2):
x = row[i]
y = x ^1if row[i+1] != y:
j = pos[y]
row[i+1], row[j] = row[j], row[i+1]
pos[row[j]] = j
pos[row[i+1]] = i+1 ans +=1return ans
impl Solution {
pubfnmin_swaps_couples(row: Vec<i32>) -> i32 {
let n = row.len();
letmut row = row;
letmut pos =vec![0; n];
for (i, &v) in row.iter().enumerate() {
pos[v asusize] = i;
}
letmut ans =0;
letmut i =0;
while i < n {
let x = row[i];
let y = x ^1;
if row[i+1] != y {
let j = pos[y asusize];
row.swap(i+1, j);
pos[row[j] asusize] = j;
pos[row[i+1] asusize] = i+1;
ans +=1;
}
i +=2;
}
ans
}
}