Couples Holding Hands

Master this topic with zero to advance depth.

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])); }
}

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