Problem statement

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

Solution

Actually, not hard problem at all: first of all, let us divide all numbers by 2, so we have 0, 0, 1, 1, ..., n-1, n-1 permutation now. Imagine example [0, 1, 1, 0, 2, 2, 3, 4, 5, 4, 3, 5] now. We can see it as n 2-seats places, and create connection between each two seats in this place. Then degree of each node is equal to 2 and it means that all graph can be separated into loops: 0 -> 1 -> 0, 2 -> 2, 3 -> 4 -> 5 -> 3]. What we need to return now is just n minus number of loops we have.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def minSwapsCouples(self, row):
        graph = defaultdict(set)
        comps, seen, it, n = defaultdict(list), set(), 0, len(row)//2
        
        for i in range(n):
            graph[row[2*i]//2].add(row[2*i+1]//2)
            graph[row[2*i+1]//2].add(row[2*i]//2)
            
        def dfs(node, i):
            comps[i].append(node)
            seen.add(node)
            for neib in graph[node]:
                if neib not in seen: dfs(neib, i)
                    
        for j in range(n):
            if j not in seen:
                dfs(j, it)
                it += 1
                
        return n - len(comps)

Remark

The same algorithm can be implement with Union Find.