https://leetcode.com/problems/couples-holding-hands/

The solutions to these kinds of problems all come down to one mathematical idea, permutation graph, no matter you are using union-find, greedy, or cycle decomposition. And once you understand the concept of permutation graph, you will know how to think about it when you next time encountering them. So, I'm going to detour a little bit to talk about the permutation graph.

Permutation Graph and Graph Decomposition

The permutation graph theory clams that given a pair of permutation, e.g, group1:a,b,a,c,a,d,c and group2:b,c,d,a,a,c,a, if we connect the edge from group1 to group2, we can represent this pair of permutation by a graph. Based on observation, if at one position i, we have group1[i]=group[i], then this vertex should have a self-connected edge.

To transform group2 into group1, we need to make swapping so that we can remove edges between two vertices(in other words, let them become self-connected edges).

Then, another observation you need is that for any cycle in our graph, the minimal steps to remove all non-self-connected edges for a cycle is the number of edges minus 1,#edges-1. Hence, the total number of swap:

#swap=∑(Ck−1)#swap=∑(Ck​−1) where C1,…,CkC1​,…,Ck​ are the lengths of the cycles(connected components) in our graph.

If we want to minimize the total #swap, we need to find a way to decompose our graph into different cycles so that each cycle is as small as possible(Because the number of edges is fixed, but if the more cycles we ended with, the more times #swap is minus by 1).

The more general visual example is given in this post: (854. K-Similar Strings)[]. Actually, in this question, we don't need to decompose the graph because each vertex only has 2 degrees and there is only one way to decompose the graph. I'll talk this later.

For more detailed information about cycle decomposition, you can check this video

Those are all the prerequisite knowledge to solve this question. Let's back to our problem.

Union-Find

The problem defines a bunch of couples, e.g, [0,1] , [1,2], [3,4]. Without loss of generality, Let's name [0,1] couple A, [2,3] couple B and so on. To smooth our understanding, let's say we have a function named 'coupleOf()'. According to our definition, we have coupleOf(0)=A, coupleOf(1)=A, 'coupleOf(2)=B', coupleOf(3)=B. A,B can denote vertices in the graph and for each pair in the row, row[2*i] and row2*i+1, we connect the edge from coupleOf(row[2*i]) to coupleOf(row[2*i+1]).

Given a row = [0,2,3,4,5,1,6,8,7,9], we can visualize them as follows:

According to permutation graph theory, the minimal step of optimal swapping(the swap which at least help match one couple) is #swap=∑(Ck−1)#swap=∑(Ck​−1) where C1,…,CkC1​,…,Ck​ are the lengths of the cycles(connected components) in our graph.

Notice that in this question, every vertex only has 2 degrees, and there is only one way to decompose our graph into cycles(which is very obvious) so that the problem could be reduced into #swap = #(vertex) - #num(components). In the end, we only need to count the number of connected components, and this can be solved by using DFS or Union-Find.

Greedy Policy

So far, we have already found a way to solve this question in O(n) time. If you look at the graph above more carefully, there is a greedy policy. Since there is only one way to decompose graph, any swap that helps match at least one couple is a greedy action.

Specifically, we can use one loop to precompute a hash map, position, which used to store the position of each person. Then we loop over the row again, whenever we find a pair of people not match, we can find where the corresponding mate is in position and swap them. We keep doing these greedy actions and count how many swapping we need.

class Solution(){
    private int count = 0;
    private HashMap<Integer, Integer> position = new HashMap<>();
    public int minSwapsCouples(int[] row) {
        for (int i = 0; i < row.length; i++) {
            this.position.put(row[i], i);
        }
        for (int g = 0; g < row.length / 2; g++) {
            int c1 = row[2*g];
            int c2 = row[2*g+1];
            if((c1%2==0 && c2!=c1+1) || (c1%2!=0 &&c2!=c1-1)){
                int source_int = row[2 * g];
                int target_pos = source_int
                        % 2 == 0 ? position.get(source_int + 1) : position.get(source_int - 1);
                swap(row, 2 * g+1, target_pos);
                count++;
            }
        }
        return count;
    }
    private void swap(int[] row, int i, int j) {
        int tmp = row[i];
        row[i] = row[j];
        row[j] = tmp;
        this.position.put(row[i], i);
        this.position.put(row[j], j);
    }
}