Here, We see Couples Holding Hands LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Couples Holding Hands LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Couples Holding Hands LeetCode Solution
Table of Contents
Problem Statement
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.
Couples Holding Hands LeetCode Solution C++
class Solution {
public:
int minSwapsCouples(vector<int>& row) {
int n = size(row);
int ans = 0;
vector<int> vis(n,0);
unordered_map<int,int> m;
for(int i=0;i<n;++i) m[row[i]] = i;
for(int i=0;i<n;i+=2){
if(!vis[i]){
int pa = i;
int pb = -1;
int loopEdge = 0;
while(!vis[pa]){
if(row[pa]%2==0) pb = m[row[pa]+1];
else pb = m[row[pa]-1];
vis[pa] = vis[pb] = 1;
pa = pb;
pb = -1;
if(pa%2==0) ++pa;
else --pa;
++loopEdge;
}
ans += loopEdge-1;
}
}
return ans;
}
};
Code language: PHP (php)
Couples Holding Hands LeetCode Solution Java
class Solution {
public int minSwapsCouples(int[] row) {
int n=row.length;
int swaps=0;
for(int i=0;i<n;i+=2){
int couple=row[i]%2==0 ? row[i]+1 : row[i]-1;
if(row[i+1]!=couple){
swaps++;
for(int j=i+1;j<n;j++){
if(row[j]==couple){
row[j]=row[i+1];
row[i+1]=couple;
break;
}
}
}
}
return swaps;
}
}
Code language: PHP (php)
Couples Holding Hands LeetCode Solution JavaScript
var minSwapsCouples = function (row) {
let res = 0;
for (let i = 0; i < row.length - 1; i += 2) {
let pair = 0;
if (row[i] % 2 === 0) {
pair = row[i] + 1;
} else pair = row[i] - 1;
if (row[i + 1] === pair) continue;
for (j = i; j < row.length; j++) {
if (row[j] === pair) {
row[j] = row[i + 1];
row[i + 1] = pair;
res++;
break;
}
}
}
return res;
};
Code language: JavaScript (javascript)
Couples Holding Hands Solution Python
class Solution(object):
def minSwapsCouples(self, row):
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rootX = find(x)
rootY = find(y)
if rootX != rootY:
parent[rootX] = rootY
n = len(row) // 2
parent = [i for i in range(n)]
for i in range(0, len(row), 2):
union(row[i] // 2, row[i+1] // 2)
count = sum([1 for i, x in enumerate(parent) if i == find(x)])
return n - count