Minimum Number of Swaps to Arrange Couples

We are given 2×N seats, where N couples are sitting in random order. Our task is to rearrange them so that each couple is sitting together. A couple is identified by having two consecutive seat positions. We need to determine the minimum number of swaps required to achieve this arrangement.

Key Insights:

  1. Pair Identification: Each individual has a unique identifier, but we can say that persons i and i+1 form a couple (or any unique pair). For instance, if persons are indexed from 0, then a couple could be (0,1),(2,3),…,(2×N−2,2×N−1).
  2. Swaps: A swap can be considered as exchanging the positions of two people. The goal is to reduce the number of mismatched pairs in the least number of swaps.

Approach:

This problem can be mapped as a minimum swap problem in a permutation. We’ll use greedy swaps to correct the position of each person to form couples side-by-side.

Steps:

Create a mapping:

We’ll create a map that links each person to their partner. For instance, if person 0 is the partner of person 1, and 2 is the partner of person 3, this will be used to easily identify the correct couple positions.

Iterate through the row:

For each couple, check if they are sitting together. If not, we will perform a swap with the person’s actual partner, using the mapping created.

Count swaps:

Each time we swap two persons to correct their position, we increment the count of swaps.

Solution:

Here’s the TypeScript implementation that solves the problem efficiently:

function minSwapsCouples(row: number[]): number {
    const n = row.length / 2;
    const partner = new Map<number, number>();
    
    // Create mapping for each couple's position
    for (let i = 0; i < row.length; i++) {
        partner.set(row[i], i);
    }

    let swaps = 0;

    // Loop through each couple position
    for (let i = 0; i < n * 2; i += 2) {
        const firstPerson = row[i];
        const secondPerson = row[i + 1];
        const correctPartner = firstPerson % 2 === 0 ? firstPerson + 1 : firstPerson - 1;

        // If the current person is not sitting with their partner, swap them
        if (secondPerson !== correctPartner) {
            swaps++;

            // Find the partner's current position
            const partnerIndex = partner.get(correctPartner)!;

            // Swap the second person with the correct partner
            row[partnerIndex] = secondPerson;
            row[i + 1] = correctPartner;

            // Update the partner map after the swap
            partner.set(secondPerson, partnerIndex);
            partner.set(correctPartner, i + 1);
        }
    }

    return swaps;
}

Explanation:

  1. Mapping Partners: We create a partner map that stores each person’s current position. This helps us quickly find where a person’s partner is sitting.
  2. Iterate in Pairs: We loop through the list in steps of two (since each person in the row should sit with their partner).
  3. Check and Swap: For each pair, we check if the two people are already partners. If not, we swap the current person’s seat with their partner and update the map accordingly.
  4. Counting Swaps: We count every swap performed.

Time Complexity:

  • Time Complexity: O(N) since we are making at most N swaps, where N is the number of couples. Creating and updating the map and performing swaps is also linear.
  • Space Complexity: O(N) due to the map storing the positions of each person.
const row = [0, 2, 1, 3];
console.log(minSwapsCouples(row));  // Output: 1

In the example above, we only need one swap to make sure persons 0 and 1 are together, and persons 2 and 3 are together.

If you like this, please think about buying me a coffee! ☕️.

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go: