Problem statement

https://binarysearch.com/problems/Swapping-Socks/

Solution

Equal to Leetcode 0765 Couples Holding Hands.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, row):
        G = defaultdict(set)
        comps, seen, it, n = defaultdict(list), set(), 0, len(row)//2
        
        for i in range(n):
            G[row[2*i]//2].add(row[2*i+1]//2)
            G[row[2*i+1]//2].add(row[2*i]//2)
            
        def dfs(node, i):
            comps[i].append(node)
            seen.add(node)
            for neib in G[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)