# LeetCode 765: Couples Holding Hands

## Problem Restatement

We are given a row of seats.

There are `n` couples, so there are `2n` people.

People are numbered from `0` to `2n - 1`.

Couples are paired in order:

| Couple | People |
|---:|---|
| `0` | `0, 1` |
| `1` | `2, 3` |
| `2` | `4, 5` |

In general, person `x` has partner:

```python
x ^ 1
```

This works because:

```text
0 ^ 1 = 1
1 ^ 1 = 0
2 ^ 1 = 3
3 ^ 1 = 2
```

We may swap any two people.

Return the minimum number of swaps needed so that every couple sits side by side. The statement asks for the minimum swaps, where one swap chooses any two people and switches their seats.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `row`, where `row[i]` is the person sitting in seat `i` |
| Output | Minimum number of swaps |
| Couple rule | People `0,1` are a couple, `2,3` are a couple, and so on |
| Swap rule | Any two people may be swapped |

Example function shape:

```python
def minSwapsCouples(row: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
row = [0, 2, 1, 3]
```

Output:

```python
1
```

The seats are:

```text
[0, 2] [1, 3]
```

Person `0` should sit with person `1`.

Person `1` is currently at seat `2`.

Swap the people at seats `1` and `2`:

```python
[0, 1, 2, 3]
```

Now both couples sit together.

Example 2:

```python
row = [3, 2, 0, 1]
```

Output:

```python
0
```

The pairs are:

```text
[3, 2] [0, 1]
```

Person `3` sits with `2`, and person `0` sits with `1`.

So no swap is needed.

## First Thought: Fix One Seat Pair at a Time

Seats naturally form pairs:

```text
(0, 1), (2, 3), (4, 5), ...
```

For each pair, if the two people are already a couple, do nothing.

If not, we can fix this pair with exactly one swap.

Suppose the pair is:

```python
[a, b]
```

Person `a` should sit with:

```python
a ^ 1
```

If seat `i + 1` does not contain `a ^ 1`, find where `a ^ 1` is sitting, and swap that person into seat `i + 1`.

This fixes the current pair permanently.

## Key Insight

A greedy approach works because once we fix seats `i` and `i + 1`, we never need to touch them again.

At seat pair `(i, i + 1)`:

1. Let `first = row[i]`.
2. The correct partner is `first ^ 1`.
3. If `row[i + 1]` is already the partner, the pair is done.
4. Otherwise, swap the partner into seat `i + 1`.

This uses one swap and creates a valid couple in the current pair.

Since every invalid seat pair needs at least one change involving one of its seats, this greedy repair is optimal.

## Position Map

To find a person's current seat quickly, keep a dictionary:

```python
pos[person] = seat_index
```

Example:

```python
row = [0, 2, 1, 3]
```

The position map is:

```python
{
    0: 0,
    2: 1,
    1: 2,
    3: 3,
}
```

When we need person `1`, we can find their seat immediately:

```python
pos[1] == 2
```

After swapping two people, we must update their positions in the map.

## Algorithm

1. Build `pos`, mapping each person to their seat index.
2. Initialize `swaps = 0`.
3. Process seats two at a time: `0, 2, 4, ...`.
4. Let:
   1. `first = row[i]`
   2. `partner = first ^ 1`
5. If `row[i + 1] == partner`, continue.
6. Otherwise:
   1. Find `partner_index = pos[partner]`.
   2. Swap `row[i + 1]` with `row[partner_index]`.
   3. Update `pos`.
   4. Increment `swaps`.
7. Return `swaps`.

## Correctness

The algorithm processes seat pairs from left to right.

When it starts processing pair `(i, i + 1)`, all earlier pairs are already valid couples. The algorithm never changes earlier seats again, because it only swaps the person at seat `i + 1` with a later or current unfixed seat.

If `row[i + 1]` is already the partner of `row[i]`, this pair is already correct, and no swap is needed.

Otherwise, the partner of `row[i]` must be somewhere else in the row. To make seat `i` part of a valid couple, that partner must eventually be placed next to `row[i]`. The algorithm performs exactly that swap immediately, putting the partner into seat `i + 1`.

After this swap, pair `(i, i + 1)` is valid and remains valid for the rest of the algorithm.

Each invalid pair processed by the algorithm requires one swap, and the algorithm uses exactly one swap to fix it. Since every processed pair is fixed permanently and no unnecessary swaps are made, the total number of swaps is minimum.

## Complexity

Let `n = len(row)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the row once and use constant-time lookups |
| Space | `O(n)` | The position map stores every person |

## Implementation

```python
class Solution:
    def minSwapsCouples(self, row: list[int]) -> int:
        pos = {}

        for i, person in enumerate(row):
            pos[person] = i

        swaps = 0

        for i in range(0, len(row), 2):
            first = row[i]
            partner = first ^ 1

            if row[i + 1] == partner:
                continue

            partner_index = pos[partner]
            other = row[i + 1]

            row[i + 1], row[partner_index] = row[partner_index], row[i + 1]

            pos[partner] = i + 1
            pos[other] = partner_index

            swaps += 1

        return swaps
```

## Code Explanation

We first build the position map:

```python
pos = {}

for i, person in enumerate(row):
    pos[person] = i
```

This allows us to locate any person in constant time.

Then we process seat pairs:

```python
for i in range(0, len(row), 2):
```

For the first person in the pair:

```python
first = row[i]
partner = first ^ 1
```

The expression `first ^ 1` gives the correct partner.

If the partner is already sitting next to them:

```python
if row[i + 1] == partner:
    continue
```

we do nothing.

Otherwise, find the partner's current seat:

```python
partner_index = pos[partner]
```

The person currently sitting in seat `i + 1` will be moved away:

```python
other = row[i + 1]
```

Now swap:

```python
row[i + 1], row[partner_index] = row[partner_index], row[i + 1]
```

After the swap, we update the position map:

```python
pos[partner] = i + 1
pos[other] = partner_index
```

Finally, count the swap:

```python
swaps += 1
```

## Alternative: Union-Find View

There is also a graph solution.

Person `x` belongs to couple:

```python
x // 2
```

For each adjacent seat pair, union the two couple IDs sitting together.

If a connected component contains `k` couples, it needs `k - 1` swaps to fix.

So the answer is:

```text
number of couples - number of connected components
```

This gives the same result, but the greedy position-map solution is usually simpler to implement.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minSwapsCouples([0, 2, 1, 3]) == 1
    assert s.minSwapsCouples([3, 2, 0, 1]) == 0
    assert s.minSwapsCouples([1, 0]) == 0
    assert s.minSwapsCouples([0, 3, 2, 1]) == 1
    assert s.minSwapsCouples([5, 4, 2, 6, 3, 1, 0, 7]) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[0,2,1,3]` | Main example requiring one swap |
| `[3,2,0,1]` | Already valid |
| `[1,0]` | One couple reversed is still valid |
| `[0,3,2,1]` | One misplaced partner |
| Larger mixed row | Multiple repairs needed |