LC-0765 Hard LeetCode

765. Couples Holding Hands

Greedy Depth-First Search Breadth-First Search Union Find Graph

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 58% Topics: Greedy, Depth-First Search, Breadth-First Search, Union Find, Graph

Reading material

Greedy 11 min Trees & Traversals 18 min Union–Find (DSU) 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def minSwapsCouples(self, row):
        """
        :type row: List[int]
        :rtype: int
        """
        N = len(row)//2
        couples = [[] for _ in xrange(N)]
        for seat, num in enumerate(row):
            couples[num//2].append(seat//2)
        adj = [[] for _ in xrange(N)]
        for couch1, couch2 in couples:
            adj[couch1].append(couch2)
            adj[couch2].append(couch1)

        result = 0
        for couch in xrange(N):
            if not adj[couch]: continue
            couch1, couch2 = couch, adj[couch].pop()
            while couch2 != couch:
                result += 1
                adj[couch2].remove(couch1)
                couch1, couch2 = couch2, adj[couch2].pop()
        return result  # also equals to N - (# of cycles)

Solution from kamyu104/LeetCode-Solutions · MIT