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:

In general, person x has partner:

x ^ 1

This works because:

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

Example function shape:

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

Examples

Example 1:

row = [0, 2, 1, 3]

Output:

1

The seats are:

[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:

[0, 1, 2, 3]

Now both couples sit together.

Example 2:

row = [3, 2, 0, 1]

Output:

0

The pairs are:

[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:

(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:

[a, b]

Person a should sit with:

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:

pos[person] = seat_index

Example:

row = [0, 2, 1, 3]

The position map is:

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

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

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

Implementation

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:

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:

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

For the first person in the pair:

first = row[i]
partner = first ^ 1

The expression first ^ 1 gives the correct partner.

If the partner is already sitting next to them:

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

we do nothing.

Otherwise, find the partner’s current seat:

partner_index = pos[partner]

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

other = row[i + 1]

Now swap:

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

After the swap, we update the position map:

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

Finally, count the swap:

swaps += 1

Alternative: Union-Find View

There is also a graph solution.

Person x belongs to couple:

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:

number of couples - number of connected components

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

Testing

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: