Couples Holding Hands: Greedy Swaps and Union-Find

There are n couples sitting in 2n seats arranged in a row. You want every couple to sit side by side. Couple i consists of person 2i and person 2i + 1. In each swap, you pick any two people and have them switch seats. Return the minimum number of swaps needed so that every couple is sitting next to each other.

This is LeetCode 765: Couples Holding Hands, and it is one of those problems where a greedy approach gives you an optimal answer, but understanding why requires thinking about cycles in a graph.

Why this problem matters

Couples Holding Hands teaches two important concepts at once. First, it shows how a greedy "fix the current pair" strategy can produce the globally optimal result. Second, it connects to cycle decomposition in permutations, which is a technique that appears in sorting problems, puzzle problems, and anywhere you need to count minimum swaps. If you can see the connection between greedy swapping and cycle counting, you unlock a whole family of related problems.

The greedy approach

Look at seats two at a time: seats 0-1, then seats 2-3, then seats 4-5, and so on. For each pair of seats, check if the two people sitting there are a couple. If they are, move on. If they are not, find the partner of the person in the first seat and swap that partner into the second seat.

This greedy strategy works because fixing one pair never breaks a pair that was already correct. Each swap places exactly one couple in their final positions, so you never need to revisit a pair.

def minSwapsCouples(row):
    n = len(row)
    pos = {person: i for i, person in enumerate(row)}

    swaps = 0
    for i in range(0, n, 2):
        partner = row[i] ^ 1
        if row[i + 1] != partner:
            j = pos[partner]
            row[i + 1], row[j] = row[j], row[i + 1]
            pos[row[j]] = j
            pos[row[i + 1]] = i + 1
            swaps += 1

    return swaps

The key trick is row[i] ^ 1. XOR with 1 flips the last bit, which maps person 2k to 2k + 1 and vice versa. This gives you the partner of any person in O(1) time.

The pos dictionary maps each person to their current seat index, so you can find where the partner is sitting in O(1) time. After each swap, you update pos for both people who moved.

Walking through the swaps

In this example, the initial arrangement is [0, 2, 1, 3, 5, 4, 7, 6]. The first pair of seats holds person 0 and person 2. Person 0's partner is person 1 (since 0 ^ 1 = 1), so we swap person 2 with person 1. After that single swap, every pair of seats holds a valid couple, and the algorithm finishes with just 1 swap.

Notice that pairs like (5, 4) and (7, 6) are already couples even though the smaller number comes second. The algorithm does not care about ordering within a pair, only that both members of the couple are adjacent.

The union-find perspective

There is an elegant alternative way to think about this problem. Treat each pair of seats as a node and each couple as a connection. For seat pair i (seats 2i and 2i + 1), the two people sitting there belong to some couples. If both people belong to the same couple, that seat pair is self-contained. If they belong to different couples, you need to connect those seat pairs.

Build a union-find structure over seat pairs. For each seat pair, union the couple IDs of the two people sitting there. After processing all seat pairs, you will have some number of connected components. Each component of size k requires exactly k - 1 swaps to fix. The total minimum swaps is n - number_of_components, where n is the number of couples.

def minSwapsCouples(row):
    n = len(row) // 2
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx != ry:
            parent[ry] = rx
            return True
        return False

    swaps = 0
    for i in range(0, len(row), 2):
        couple_a = row[i] // 2
        couple_b = row[i + 1] // 2
        if union(couple_a, couple_b):
            swaps += 1

    return swaps

Every time union returns True, it means two different couples were tangled together in the same seat pair, and that requires one swap. The total count of successful unions equals the minimum number of swaps.

Complexity analysis

Both approaches are linear in practice. The greedy approach does a single pass over the seat pairs. The union-find approach processes each seat pair once, and each union/find operation is nearly O(1) amortized thanks to path compression.

Edge cases to watch for

• Already sorted: if every couple is already adjacent, the algorithm does zero swaps. The greedy version skips every pair and the union-find version never merges different components.
• Two people, one couple: the smallest input is row = [0, 1] or row = [1, 0]. Both require zero swaps.
• Worst case arrangement: when no couple is adjacent, the number of swaps equals n - 1 for n couples. This happens when every pair of seats mixes two different couples and they form one large cycle.
• XOR partner logic: make sure you use row[i] ^ 1 and not row[i] + 1 or row[i] - 1. The XOR approach correctly handles both even and odd person IDs without branching.

The building blocks

This problem combines two patterns you will see again and again.

Greedy local fixing. When you can fix a local constraint without violating any previously fixed constraints, a greedy approach works. This same principle appears in problems like Candy (fix left-to-right, then right-to-left) and Gas Station (reset the start when the tank goes negative).

Cycle decomposition. The union-find solution counts cycles in a permutation. A permutation with k cycles needs exactly n - k swaps to sort. This is a fundamental result in combinatorics that shows up in minimum-swap problems, puzzle state problems, and string transformation problems.

From understanding to recall

You have traced through the greedy approach and seen why it works. You have also seen the union-find perspective and how cycle counting gives you the same answer. But here is the thing: these details fade fast. In a week, you might remember that the problem involves couples and swaps, but will you remember the row[i] ^ 1 trick? Will you remember that the number of swaps equals the number of successful unions?

The gap between "I understood it once" and "I can write it cold" is real. Spaced repetition closes that gap. Practice the greedy template a few times at increasing intervals, and the XOR partner trick becomes automatic. Practice the union-find template, and you stop thinking about the mechanics of find and union and start thinking about what the components mean.

Related posts

• Redundant Connection - Union-Find for cycle detection in an undirected graph, the same data structure applied to a different problem
• Number of Provinces - Counting connected components with Union-Find, a simpler version of the cycle counting idea used here
• Accounts Merge - Union-Find to group items by shared attributes, another practical application of the same template

CodeBricks breaks Couples Holding Hands into its greedy and union-find building blocks and drills them individually with spaced repetition. You practice the XOR partner trick, the position map swap, and the union-find template until they are automatic. When a minimum-swap problem shows up in your interview, you do not hesitate. You just write it.