Skip to content

Couples Holding Hands⚓︎

Link

Description⚓︎

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 i-th 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.

Constraints:

  • 2n == row.length
  • 2 <= n <= 30
  • n is even.
  • 0 <= row[i] < 2n
  • All the elements of row are unique.

Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private:
    int p[31];
    void unionSets(int a, int b) {
        p[find(a)] = find(b);
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size(), m = n / 2;
        for (int i = 0; i < m; i++) p[i] = i;

        for (int i = 0; i < n; i += 2) 
            unionSets(row[i] / 2, row[i + 1] / 2);

        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (i == find(i)) cnt++;
        }
        return m - cnt;
    }
};

Another way of writing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
private:
    int p[31];
    int sets;

    void build(int m) {
        for (int i = 0; i < m; i++) p[i] = i;
        sets = m;
    }

    int find(int i) {
        if (i != p[i]) p[i] = find(p[i]);
        return p[i];
    }

    void unionSets(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            p[fx] = fy;
            sets--; 
        }
    }

public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        build(n / 2);
        for (int i = 0; i < n; i += 2) {
            unionSets(row[i] / 2, row[i + 1] / 2);
        }
        return n / 2 - sets;
    }
};