Last updated on October 9th, 2024 at 06:23 pm

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

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.

1. 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;
    }
};

2. 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;
    }
}

3. 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;
};

4. 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