Couples Holding Hands - Leetcode Solution

The "Couples Holding Hands" problem on LeetCode asks us to find the minimum number of swaps needed to make all couples next to each other. We are given an array of integers where each integer represents a person in a line of n people. The array represents which person each person in the line is paired with. For example, array [0, 2, 1, 3] represents person 0 is paired with person 2, person 1 is paired with person 3, and so on.

We can start by understanding the problem and breaking it down into smaller steps. The first step is to identify the pairs that are not sitting next to each other. If we can identify these pairs, we can swap them and make them sit next to each other.

To identify the pairs that are not sitting next to each other, we can divide the array into subarrays of size two. For example, if the array is [0, 2, 1, 3], we can divide it into [(0,2), (1,3)]. We can then iterate through the subarrays and check if the pairs are sitting next to each other. If a pair is not sitting next to each other, we can swap the second person in the pair with the person next to them, and increment the swap count by 1.

We can then repeat this process until all the couples are sitting next to each other. Once all the couples are sitting next to each other, we can return the swap count.

Here is the Java code that implements this solution:

public int minSwapsCouples(int[] row) {
    int n = row.length;
    int[] position = new int[n];
    int swaps = 0;
    
    for (int i = 0; i < n; i++) {
        position[row[i]] = i;
    }
    
    for (int i = 0; i < n; i += 2) {
        int pair1 = row[i];
        int pair2 = pair1 ^ 1;
        
        if (row[i+1] != pair2) {
            int j = position[pair2];
            swap(row, i+1, j);
            position[pair2] = i+1;
            position[row[j]] = j;
            swaps++;
        }
    }
    
    return swaps;
}

private void swap(int[] row, int i, int j) {
    int temp = row[i];
    row[i] = row[j];
    row[j] = temp;
}

In this solution, we first create an array position that stores the position of every person in the line. We then iterate through the line by pairs, and check if the pairs are sitting next to each other. If a pair is not sitting next to each other, we swap the second person in the pair with the person next to them, and increment the swap count.

The swap method is a helper method that swaps two elements in the array.

This solution runs in O(n) time and O(n) space.

1