Couples Holding Hands

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

Couples Holding Hands

There are

n

couples sitting in

2n

seats. Every couple is assigned IDs

(2i, 2i+1)

. Return the minimum number of swaps so that every couple is sitting side by side.

Mathematical Insight

This is a permutation decomposition problem. If we have

N

couples and they form

C

cycles (connected components of incorrectly paired couples), the number of swaps needed is

N - C

Hard

Examples

Input: row = [0,2,1,3]
Output: 1

Approach 1

Level II: Greedy Swaps

Intuition

Iterate through the seats in pairs. For each seat

i

and

i+1

, if they are not already a couple, find where the partner of the person at seat

i

is sitting and swap them into seat

i+1

. This local greedy strategy is optimal.

⏱ O(N^2) for finding the partner each time.💾 O(1).

java

class Solution {
    public int minSwapsCouples(int[] row) {
        int swaps = 0;
        for (int i = 0; i < row.length; i += 2) {
            int partner = row[i] ^ 1;
            if (row[i + 1] != partner) {
                swaps++;
                for (int j = i + 2; j < row.length; j++) {
                    if (row[j] == partner) {
                        int temp = row[j]; row[j] = row[i + 1]; row[i + 1] = temp;
                        break;
                    }
                }
            }
        }
        return swaps;
    }
}

Approach 2

Level III: Union-Find (Cycle Decomposition)

Intuition

Each pair of seats

(0,1), (2,3), \dots

should hold a couple. If seat pair

j

holds parts of couple

A

and couple

B

, union

A

and

B

. The number of swaps is total couples minus number of components.

⏱ O(N \cdot \alpha(N)).💾 O(N).

java

class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length / 2;
        int[] p = new int[n]; for(int i=0; i<n; i++) p[i]=i;
        int count = n;
        for(int i=0; i<row.length; i+=2) {
            int c1 = row[i]/2, c2 = row[i+1]/2;
            int r1=find(p,c1), r2=find(p,c2);
            if(r1 != r2) { p[r1]=r2; count--; }
        }
        return n - count;
    }
    int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p,p[i])); }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready

Updated: Weekly

← Previous QuestionLongest Consecutive Sequence

Next Question →Regions Cut By Slashes

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.