Couples Holding Hands

hard graph union find greedy

Problem

2n people are seated in a row (0, 1, …, 2n − 1). Couple i is people (2i, 2i + 1). Return the minimum number of swaps so every couple sits side by side (positions 2k and 2k + 1).

Inputrow = [0, 2, 1, 3]

Output1

Swap seats 1 and 2 to get [0,1,2,3]. Each couple is adjacent.

row (comma-separated, even length)

def min_swaps_couples(row):
    pos = {p: i for i, p in enumerate(row)}
    swaps = 0
    for i in range(0, len(row), 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

function minSwapsCouples(row) {
  const pos = new Map();
  for (let i = 0; i < row.length; i++) pos.set(row[i], i);
  let swaps = 0;
  for (let i = 0; i < row.length; i += 2) {
    const partner = row[i] ^ 1;
    if (row[i + 1] !== partner) {
      const j = pos.get(partner);
      pos.set(row[i + 1], j);
      pos.set(partner, i + 1);
      [row[i + 1], row[j]] = [row[j], row[i + 1]];
      swaps++;
    }
  }
  return swaps;
}

class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) pos[row[i]] = i;
        int swaps = 0;
        for (int i = 0; i < n; i += 2) {
            int partner = row[i] ^ 1;
            if (row[i + 1] != partner) {
                int j = pos[partner];
                pos[row[i + 1]] = j;
                pos[partner] = i + 1;
                int tmp = row[i + 1]; row[i + 1] = row[j]; row[j] = tmp;
                swaps++;
            }
        }
        return swaps;
    }
}

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        vector<int> pos(n);
        for (int i = 0; i < n; i++) pos[row[i]] = i;
        int swaps = 0;
        for (int i = 0; i < n; i += 2) {
            int partner = row[i] ^ 1;
            if (row[i + 1] != partner) {
                int j = pos[partner];
                pos[row[i + 1]] = j;
                pos[partner] = i + 1;
                swap(row[i + 1], row[j]);
                swaps++;
            }
        }
        return swaps;
    }
};

Explanation

We want every couple sitting side by side using as few swaps as possible. The greedy idea is simple: go through the seats in pairs (0&1, 2&3, …) and for each left seat, drag the correct partner into the seat right next to it.

The clever trick is finding a person's partner instantly. Couple i is people 2i and 2i+1, which differ by exactly one bit. So partner = row[i] ^ 1 (XOR with 1) flips the last bit: 4 pairs with 5, 7 pairs with 6, and so on.

If the person already next to row[i] is the partner, we do nothing. Otherwise we look up where the partner currently sits using the pos map, swap it into seat i+1, update the map, and count one swap.

Example: row = [0, 2, 1, 3]. Seat 0 holds 0, whose partner is 1. But seat 1 holds 2, not 1. We find 1 at index 2 and swap, giving [0, 1, 2, 3]. One swap, and the next pair 2,3 is already correct.

Each greedy fix locks one couple permanently in place, so we never undo work. Fixing one seat at a time across n pairs gives the minimum number of swaps.

Time: O(n) Space: O(n)