Last updated on March 2nd, 2025 at 03:38 pm

Here, we see a Couples Holding Hands LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Tree

Level of Question

Hard

Couples Holding Hands LeetCode Solution

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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Union-Find (Disjoint Set Union)”. This pattern is commonly used to solve problems involving connected components, cycles, or grouping elements based on relationships. The Python implementation explicitly uses the Union-Find approach, while the C++, Java, and JavaScript implementations use variations of graph traversal or swapping logic to achieve the same result.

3. Code Implementation in Different Languages

3.1 Couples Holding Hands 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;
    }
};

3.2 Couples Holding Hands 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.3 Couples Holding Hands 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;
};

3.4 Couples Holding Hands 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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n2)	O(1)
JavaScript	O(n2)	O(1)
Python	O(n * α(n))	O(n)

where, α(n) is the inverse Ackermann function (very small, almost constant).

• The Python implementation is the most efficient in terms of time complexity due to the use of Union-Find.
• The C++ implementation is also efficient but uses more space.
• The Java and JavaScript implementations are less efficient due to their brute-force approach.