Couples Holding Hands

Problem Statement

In this problem, we are given n couples that are sitting in 2n seats, arranged in a linear row. Each person in these seats is identified uniquely by an integer, and they are coupled in a sequential manner, meaning the first couple is represented as (0, 1), the second as (2, 3), and so on until (2n-2, 2n-1).

Our objective is to determine the minimum number of swaps required so that all couples are seated next to each other. A swap is defined as two individuals standing up and exchanging their seats. This situation is modeled with an array named row, where row[i] gives the ID of the person sitting in the i-th seat.

Examples

Example 1

Input:

row = [0,2,1,3]

Output:

1

Explanation:

We only need to swap the second (row[1]) and third (row[2]) person.

Example 2

Input:

row = [3,2,0,1]

Output:

0

Explanation:

All couples are already seated side by side.

Constraints

• 2n == row.length
• 2 <= n <= 30
• n is even.
• 0 <= row[i] < 2n
• All the elements of row are unique.

Approach and Intuition

The primary challenge is to rearrange the array such that each sequential pair (2i, 2i+1) for all i from 0 to n-1 are couples according to their IDs. We need to make these arrangements by swapping any two individuals, striving to achieve this with the minimum number of swaps.

To approach this:

1. First, understand the current arrangement by mapping each individual to their current position.
2. Next, iterate through the row array, and for each odd-indexed position ensure it's coupled with the right partner (as couples are in sequential order).
3. If the current person at an odd-indexed position isn't paired with the correct partner, find the correct partner elsewhere in the array, and perform a swap.
4. Every valid swap accounts for correctly positioning a couple. Continue this process until all individuals are correctly paired with their partners.

This greedy swapping ensures that each swap contributes directly to placing a couple together, contributing to the goal of minimising the swap count.

Example 1

• Input: row = [0,2,1,3]
• Output: 1
• Explanation: The pair (2, 3) is separated by 0. By swapping 2 (at index 1) and 1 (at index 2), we couple (0, 1) and (2, 3) correctly with just one swap.

Example 2

• Input: row = [3,2,0,1]
• Output: 0
• Explanation: Here, all couples (2, 3) and (0, 1) are already positioned next to each other. Therefore, no swaps are required.

From these examples, it's clear that the correct identification of misplaced individuals and their partners and the subsequent swap is central to efficiently solving this problem.

Solutions

class Solution {
    public int swapCouples(int[] seats) {
        int swaps = 0;
        for (int i = 0; i < seats.length; i += 2) {
            int partner = seats[i];
            if (seats[i+1] == (partner ^ 1)) continue;
            swaps++;
            for (int j = i+1; j < seats.length; j++) {
                if (seats[j] == (partner ^ 1)) {
                    seats[j] = seats[i+1];
                    seats[i+1] = partner ^ 1;
                    break;
                }
            }
        }
        return swaps;
    }
}