# Couples Holding Hands
**Difficulty:** HARD
[External](https://leetcode.com/problems/couples-holding-hands)
Canonical: https://scaleengineer.com/dsa/problems/couples-holding-hands
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
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.

**Constraints:**

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

# Approaches
## Greedy Approach with Linear Search
This approach iterates through the row, processing two seats at a time (a seat pair). For each seat pair, it ensures the two people sitting there form a couple. If they don't, it finds the correct partner for the first person in the pair by searching the rest of the row and then swaps them into the adjacent seat. This greedy choice is optimal because each swap resolves a seat pair permanently, reducing the problem to a smaller subproblem on the remaining seats.
**Time:** O(N^2), where N is the number of couples (i.e., `n` in the problem description, or `row.length / 2`). The outer loop runs N times. For each iteration, the inner linear search can take up to O(N) time in the worst case. This gives a total time complexity of O(N*N) = O(N^2). · **Space:** O(1), as we only use a few variables to keep track of the swaps and loop indices. The swaps are performed in-place on the input array.
**Pros:** Simple to understand and implement.; It is a space-efficient solution, requiring only O(1) extra space.
**Cons:** The nested loop structure results in a quadratic time complexity, `O(N^2)`, which is inefficient for large inputs. While the constraints of this problem are small, this approach would not scale well.
### Explanation
We iterate through the `row` array with a step of 2, focusing on seat pairs `(i, i+1)`. For each `i`, we look at the person in seat `i`, let's call them `p1 = row[i]`. We determine their partner, `partner = p1 ^ 1`. We then check if the person in the adjacent seat, `row[i+1]`, is the correct partner. If `row[i+1] == partner`, the couple is already together, and we move to the next pair of seats. If not, we must find the `partner`'s current location. We perform a linear search for `partner` in the rest of the array (from index `i+2` onwards). Once we find `partner` at index `j`, we swap the person at `i+1` with the person at `j`. This action costs one swap. We increment our swap counter. After the swap, the pair at `(i, i+1)` is now a correct couple. We repeat this process for all seat pairs. The final count is the minimum number of swaps required.

```java
class Solution {
    public int minSwapsCouples(int[] row) {
        int swaps = 0;
        for (int i = 0; i < row.length; i += 2) {
            int p1 = row[i];
            int partner = p1 ^ 1;
            if (row[i + 1] != partner) {
                swaps++;
                for (int j = i + 2; j < row.length; j++) {
                    if (row[j] == partner) {
                        int temp = row[i + 1];
                        row[i + 1] = row[j];
                        row[j] = temp;
                        break;
                    }
                }
            }
        }
        return swaps;
    }
}
```
### Algorithm
- Initialize a `swaps` counter to 0.
- Iterate through the `row` array with a step of 2, from `i = 0` to `row.length - 2`.
- For each `i`, identify the person in the first seat of the pair, `p1 = row[i]`.
- Determine the required partner for `p1`, which is `partner = p1 ^ 1` (using XOR is a concise way to find the partner, e.g., `0^1=1`, `1^1=0`, `2^1=3`, `3^1=2`).
- Check if the person in the adjacent seat, `row[i+1]`, is the `partner`.
- If `row[i+1]` is not the `partner`, we need to find the `partner` and swap them into this seat.
  - Increment the `swaps` counter.
  - Perform a linear search for the `partner` in the rest of the array, starting from index `i + 2`.
  - Once the `partner` is found at index `j`, swap the elements `row[i+1]` and `row[j]`.
- After the loop finishes, return the total `swaps` count.

## Greedy Approach with Position Map
This approach is an optimization of the previous greedy strategy. The bottleneck in the first approach was the `O(N)` linear search to find the partner's location. We can eliminate this search by pre-processing the `row` array to store the index of each person in a hash map or, more efficiently, an array since the person IDs are contiguous. This allows us to find any person's location in `O(1)` time, bringing the overall time complexity down to linear.
**Time:** O(N), where N is the number of couples. Populating the `pos` array takes `O(2n)` time. The main loop runs `n` times, and all operations inside (lookups, swaps, and updates) are `O(1)`. The total time complexity is linear. · **Space:** O(N), where N is the number of couples. We use an auxiliary array `pos` of size `2n` to store the positions of each person.
**Pros:** Highly efficient with a linear time complexity.; Maintains the intuitive logic of the greedy approach while significantly improving performance.
**Cons:** Requires extra space proportional to the total number of people, which might be a concern for problems with very large `n`.
### Explanation
First, we create a mapping from each person's ID to their seat index. An array `pos` of size `2n` is perfect for this, where `pos[person_id] = seat_index`. We populate this by iterating through the input `row` once. Then, we follow the same greedy strategy as before, iterating through seat pairs `(i, i+1)`. For each `i`, we identify `p1 = row[i]` and their required `partner = p1 ^ 1`. If `row[i+1]` is not the `partner`, we need to perform a swap. Instead of searching, we directly look up the partner's position: `partner_pos = pos[partner]`. We also need to know who is currently sitting at `i+1`, let's say `p2 = row[i+1]`. We swap `row[i+1]` and `row[partner_pos]`. After swapping, we must update our `pos` array to reflect the new positions of `p2` and `partner`. The `partner` is now at `i+1`, and `p2` is now at `partner_pos`. We increment the swap counter and proceed to the next seat pair.

```java
class Solution {
    public int minSwapsCouples(int[] row) {
        int len = row.length;
        int[] pos = new int[len];
        for (int i = 0; i < len; i++) {
            pos[row[i]] = i;
        }

        int swaps = 0;
        for (int i = 0; i < len; i += 2) {
            int p1 = row[i];
            int partner = p1 ^ 1;
            if (row[i + 1] != partner) {
                swaps++;
                int partner_pos = pos[partner];
                int p2 = row[i + 1];

                // Swap in row array
                row[i + 1] = partner;
                row[partner_pos] = p2;

                // Update positions in pos array
                pos[partner] = i + 1;
                pos[p2] = partner_pos;
            }
        }
        return swaps;
    }
}
```
### Algorithm
- First, create a position map, which can be an array `pos` of size `2n`, to store the index of each person. 
- Iterate through the input `row` once to populate this map: `pos[row[i]] = i`.
- Initialize a `swaps` counter to 0.
- Iterate through the `row` array with a step of 2, from `i = 0` to `row.length - 2`.
- For each `i`, identify `p1 = row[i]` and their required `partner = p1 ^ 1`.
- If `row[i+1]` is not the `partner`:
  - Increment the `swaps` counter.
  - Find the partner's current position in O(1) time using the map: `partner_pos = pos[partner]`.
  - Identify the person who is currently in the wrong seat: `p2 = row[i+1]`.
  - Perform the swap: `row[i+1]` becomes `partner`, and `row[partner_pos]` becomes `p2`.
  - **Crucially**, update the position map to reflect the swap: `pos[partner]` is now `i+1`, and `pos[p2]` is now `partner_pos`.
- Return the total `swaps` count.

## Union-Find (Disjoint Set Union)
This approach models the problem from a graph-theoretic perspective. We can think of the `n` couples as `n` distinct nodes. The initial arrangement in the `row` array creates connections between these nodes. If a seat pair is occupied by people from two different couples, it means these two couples are 'tangled' together. We can use a Union-Find data structure to group these tangled couples into components. The key insight is that to untangle a component of `k` couples, it takes exactly `k-1` swaps. Therefore, the total minimum number of swaps is `n - (number of components)`.
**Time:** O(N * α(N)), where N is the number of couples and α is the extremely slow-growing Inverse Ackermann function. The loop runs N times, and with path compression and union by rank/size, each `union` operation takes nearly constant amortized time. For all practical purposes, this is considered linear time, O(N). · **Space:** O(N), where N is the number of couples. This space is used to store the `parent` array (and potentially a `rank` or `size` array) for the DSU data structure.
**Pros:** Provides an elegant and highly efficient solution.; Asymptotically one of the fastest known solutions for this type of problem.; Offers a powerful, abstract way to reason about connectivity and cycles.
**Cons:** The concept of Union-Find is more abstract and might be less intuitive than a direct greedy approach.; Requires implementing or using a DSU data structure, which adds a bit of overhead compared to a simple array-based greedy solution.
### Explanation
We consider `n` nodes, where each node `j` represents the couple `(2j, 2j+1)`. We initialize a Union-Find (DSU) data structure with `n` sets, one for each couple. The initial number of disjoint sets (components) is `n`. We then iterate through the `n` seat pairs. For each seat pair `i` (seats `2i` and `2i+1`), we look at the two people sitting there, `p1 = row[2i]` and `p2 = row[2i+1]`. We determine which couple each person belongs to: person `p` belongs to couple `p/2`. So, `p1` belongs to couple `c1 = p1/2`, and `p2` belongs to couple `c2 = p2/2`. The fact that members of couple `c1` and `c2` are in the same seat pair implies a dependency. We represent this by merging the sets containing `c1` and `c2` using the `union` operation. If `c1` and `c2` were already in the same set, the `union` operation does nothing. If they were in different sets, they are merged, and the total number of components decreases by one. After iterating through all `n` seat pairs, the total number of swaps is `n - (total number of components)`.

```java
class DSU {
    private int[] parent;
    private int count;

    public DSU(int n) {
        parent = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

class Solution {
    public int minSwapsCouples(int[] row) {
        int n_couples = row.length / 2;
        DSU dsu = new DSU(n_couples);

        for (int i = 0; i < row.length; i += 2) {
            int couple1 = row[i] / 2;
            int couple2 = row[i + 1] / 2;
            dsu.union(couple1, couple2);
        }

        return n_couples - dsu.getCount();
    }
}
```
### Algorithm
- The `n` couples `(0,1), (2,3), ...` are the entities we want to group. We can think of them as `n` nodes in a graph, indexed `0` to `n-1`.
- Initialize a Union-Find (DSU) data structure with `n` elements, where each element initially forms its own set. The number of components is `n`.
- Iterate through the `n` seat pairs. For each seat pair `i` (seats `2i` and `2i+1`):
  - Get the people in these seats: `p1 = row[2*i]` and `p2 = row[2*i+1]`.
  - Determine the couple ID for each person. A person `p` belongs to couple `p / 2`.
  - Let `c1 = p1 / 2` and `c2 = p2 / 2`.
  - These two couples, `c1` and `c2`, are now linked because their members are sharing a seat pair. We merge their sets using the `union(c1, c2)` operation.
- The `union` operation will merge the sets of `c1` and `c2` if they are not already in the same set, and in doing so, it decrements the total number of components.
- After iterating through all seat pairs, the total number of swaps needed is `n - (final number of components)`.

# Solutions
### CSharp

```csharp
public class Solution {
    private int[] p;
    public int MinSwapsCouples(int[] row) {
        int n = row.Length >> 1;
        p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        for (int i = 0; i < n << 1; i += 2) {
            int a = row[i] >> 1;
            int b = row[i + 1] >> 1;
            p[find(a)] = find(b);
        }
        int ans = n;
        for (int i = 0; i < n; ++i) {
            if (p[i] == i) {
                --ans;
            }
        }
        return ans;
    }
    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}
```

### Java

```java
class Solution {
private
  int[] p;
public
  int minSwapsCouples(int[] row) {
    int n = row.length >> 1;
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    for (int i = 0; i < n << 1; i += 2) {
      int a = row[i] >> 1, b = row[i + 1] >> 1;
      p[find(a)] = find(b);
    }
    int ans = n;
    for (int i = 0; i < n; ++i) {
      if (i == find(i)) {
        --ans;
      }
    }
    return ans;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSwapsCouples(vector<int> &row) {
    int n = row.size() / 2;
    int p[n];
    iota(p, p + n, 0);
    function<int(int)> find = [&](int x) -> int {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    };
    for (int i = 0; i < n << 1; i += 2) {
      int a = row[i] >> 1, b = row[i + 1] >> 1;
      p[find(a)] = find(b);
    }
    int ans = n;
    for (int i = 0; i < n; ++i) {
      ans -= i == find(i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minSwapsCouples(self, row: List[int]) -> int: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] n = len(row) >> 1 p = list(range(n)) for i in range(0, len(row), 2): a, b = row[i] >> 1, row[i + 1] >> 1 p[find(a)] = find(b) return n - sum(i == find(i) for i in range(n))

```