Code Implementation

class Solution:
    def minSwapsCouples(self, row):
        n = len(row) // 2
        pos = {person: i for i, person in enumerate(row)}
        swaps = 0
        for i in range(0, len(row), 2):
            x = row[i]
            y = x ^ 1  # partner
            if row[i + 1] != y:
                partner_idx = pos[y]
                # Swap row[i+1] and row[partner_idx]
                pos[row[i + 1]] = partner_idx
                row[partner_idx] = row[i + 1]
                row[i + 1] = y
                pos[y] = i + 1
                swaps += 1
        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 x = row[i];
            int y = x ^ 1;
            if (row[i + 1] != y) {
                int partner_idx = pos[y];
                pos[row[i + 1]] = partner_idx;
                row[partner_idx] = row[i + 1];
                row[i + 1] = y;
                pos[y] = 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 x = row[i];
            int y = x ^ 1;
            if (row[i + 1] != y) {
                int partnerIdx = pos[y];
                pos[row[i + 1]] = partnerIdx;
                row[partnerIdx] = row[i + 1];
                row[i + 1] = y;
                pos[y] = i + 1;
                swaps++;
            }
        }
        return swaps;
    }
}
      

var minSwapsCouples = function(row) {
    let n = row.length;
    let pos = new Array(n);
    for (let i = 0; i < n; i++) pos[row[i]] = i;
    let swaps = 0;
    for (let i = 0; i < n; i += 2) {
        let x = row[i];
        let y = x ^ 1;
        if (row[i + 1] !== y) {
            let partnerIdx = pos[y];
            pos[row[i + 1]] = partnerIdx;
            row[partnerIdx] = row[i + 1];
            row[i + 1] = y;
            pos[y] = i + 1;
            swaps++;
        }
    }
    return swaps;
};
      

Problem Description

You are given an array row representing couples sitting in a row. There are 2n seats and n couples, with each couple numbered as (0,1), (2,3), (4,5), ... (so person 0 is coupled with 1, 2 with 3, and so on). The array row contains the IDs of people sitting in each seat, in order.

Your goal is to find the minimum number of swaps needed so that every couple sits together (i.e., for every even index i, row[i] and row[i+1] are a couple). Each swap can exchange any two people sitting in the row.

• Each person appears exactly once in row.
• Each swap can involve any two seats.
• There is always at least one valid solution.

Thought Process

At first glance, one might consider checking every possible swap among the seats to try to bring each couple together, but this brute-force approach is inefficient and unnecessary.

Instead, notice that for each pair of seats (i and i+1), we can check if the two people are already a couple. If not, we want to swap the person at i+1 with the partner of the person at i. This way, we can fix one couple at a time, minimizing the number of swaps.

The key insight is that each swap can fix exactly one couple, and by always making the optimal swap, we can solve the problem efficiently.

Solution Approach

• Step 1: Map Positions
  First, create a mapping from each person's ID to their current seat index. This allows us to quickly find where any person is sitting.
• Step 2: Iterate in Pairs
  Loop through the array two seats at a time (i.e., indices 0, 2, 4, ...). For each pair, check if the two people are a couple.
• Step 3: Identify Partner
  For a person with ID x, their partner is always x ^ 1 (bitwise XOR with 1). For example, 0's partner is 1, 2's is 3, etc.
• Step 4: Swap if Needed
  If the person at i+1 is not the partner, swap them with the partner (wherever the partner is sitting). Update the mapping to reflect the new positions.
• Step 5: Count Swaps
  Each time a swap is made, increment the swap counter. Continue this process until all couples are together.
• Why This Works
  By always placing the partner next to their pair in one swap, we guarantee the minimum number of swaps. We use a mapping for O(1) lookups, making the algorithm efficient.

Example Walkthrough

Let's use the input row = [0, 2, 1, 3].

• Initial State: [0, 2, 1, 3]
• First Pair (indices 0 and 1):
  • Person 0 is at index 0. Their partner is 1.
  • Index 1 has person 2, not 1. So, swap person at index 1 (2) with person 1 (at index 2).
  • After swap: [0, 1, 2, 3]. Update positions.
  • Swaps: 1
• Second Pair (indices 2 and 3):
  • Person 2 is at index 2. Their partner is 3.
  • Index 3 has person 3. Already a couple, no swap needed.
• Result: All couples sit together with 1 swap.

Time and Space Complexity

• Brute-Force Approach:
  • Would check all possible swaps, leading to factorial time complexity: O((2n)!).
• Optimized Approach:
  • We go through the array once, O(n) pairs, and each lookup/swap is O(1) due to the mapping.
  • Time Complexity: O(n), where n is the number of couples.
  • Space Complexity: O(n), for the position mapping.

Summary

The "Couples Holding Hands" problem is elegantly solved by walking through the row in pairs, and, whenever a couple is not together, swapping one person with their partner. By maintaining a mapping of person to seat, each swap and lookup is efficient. This greedy, step-by-step approach ensures the minimum number of swaps, with both time and space complexity linear in the number of couples.