Couples Holding Hands Problem


Description

LeetCode Problem 765.

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:

1
2
3
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:

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


Sample C++ Code using Union Find

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
34
35
36
37
38
39
40
41
42
43
44
class UF {
public:
    UF (int n) : parent(n) {}
    
    void setParent(int x, int p) {
        parent[x] = p;
    }
    
    int find(int x) {
        if (x != parent[x])
            parent[x] = find(parent[x]);
        return parent[x];
    }
    
    bool union_find(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px == py)
            return false;
        parent[px] = py;
        return true;
    }

private:
    vector<int> parent;
};

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        if (row.empty()) return 0;
        UF uf(row.size());
        for (int i = 0; i < row.size(); i += 2) {
            uf.setParent(row[i], row[i]);
            uf.setParent(row[i+1], row[i]);
        }
        int counter = 0;
        for (int i = 0; i < row.size(); i += 2) {
            if (uf.union_find(i, i + 1))
                counter++;
        }
        return counter;
    }
};




Related Posts

Vertical Order Traversal Of A Binary Tree Problem

LeetCode 987. Given the root of a binary tree, calculate...

Univalued Binary Tree Problem

LeetCode 965. A binary tree is uni-valued if every node...

Sum Of Distances In Tree Problem

LeetCode 834. There is an undirected connected tree with n...

Smallest Subtree With All The Deepest Nodes Problem

LeetCode 865. Given the root of a binary tree, the...

Smallest String Starting From Leaf Problem

LeetCode 988. You are given the root of a binary...

Similar String Groups Problem

LeetCode 839. Two strings Xand Yare similar if we can...