Algorithm
Problem Name: 765. Couples Holding Hands
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.
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.
Constraints:
2n == row.length2 <= n <= 30nis even.0 <= row[i] < 2n- All the elements of
roware unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
unordered_map < int, int>idx;
int n = row.size();
for (int i = 0; i < n; ++i) {
idx[row[i]] = i;
}
int res = 0;
for (int i = 0; i < n; i += 2) {
if (!isCouple(row[i], row[i + 1])) {
int val = findMyCouple(row[i]);
swap(row[i + 1], row[idx[val]]);
// Update idx
idx[row[idx[val]]] = idx[val];
idx[row[i + 1]] = i + 1;
++res;
}
}
return res;
}
bool isCouple(int a, int b) {
return (!(a%2) && (b == a + 1)) || (!(b%2) && (a == b + 1));
}
int findMyCouple(int x) {
return x%2 ? x - 1 : x + 1;
}
};
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const minSwapsCouples = function (row) {
let res = 0,
N = row.length
const ptn = new Array(N).fill(0)
const pos = new Array(N).fill(0)
for (let i = 0; i < N; i++) {
ptn[i] = i % 2 === 0 ? i + 1 : i - 1
pos[row[i]] = i
}
for (let i = 0; i < N; i++) {
for (let j = ptn[pos[ptn[row[i]]]]; i !== j; j = ptn[pos[ptn[row[i]]]]) {
swap(row, i, j)
swap(pos, row[i], row[j])
res++
}
}
return res
}
function swap(arr, i, j) {
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minSwapsCouples(self, row):
res, index = 0, {num: i for i, num in enumerate(row)}
for i in range(0, len(row), 2):
if row[i] % 2 == 0 and row[i + 1] != row[i] + 1:
f = row[i + 1]
row[i + 1], row[index[row[i] + 1]] = row[i] + 1, row[i + 1]
index[row[i] + 1], index[f] = i + 1, index[row[i] + 1]
res += 1
elif row[i] % 2 != 0 and row[i + 1] != row[i] - 1:
f = row[i + 1]
row[i + 1], row[index[row[i] - 1]], index[row[i + 1]] = row[i] - 1, row[i + 1], index[row[i] - 1]
index[row[i] - 1], index[f] = i + 1, index[row[i] - 1]
res += 1
return res
Input
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0765_CouplesHoldingHands
{
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 count = 0;
for (int i = 0; i < row.Length; i += 2)
{
int x = row[i];
if (row[i + 1] == (x ^ 1)) continue;
count++;
Swap(row, pos, i + 1, pos[(x ^ 1)]);
}
return count;
}
private void Swap(int[] row, int[] pos, int x, int y)
{
int temp = row[x];
pos[temp] = y;
pos[row[y]] = x;
row[x] = row[y];
row[y] = temp;
}
}
}
Input