We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Couples Holding Hands

Number: 770

Difficulty: Hard

Paid? No

Companies: Citadel, Google

Problem Description

There are n couples sitting in 2n seats arranged in a row. Each person is represented by a unique ID, and couples are defined as (0,1), (2,3), …, (2n-2,2n-1). The task is to determine the minimum number of swaps required so that every couple is sitting side by side. A swap consists of selecting any two people and switching their seats.

Key Insights

  • Treat each couple as a group; if two people sitting together are not a true couple, they belong to different groups that need connection.
  • Modeling the problem using a union-find (disjoint set) structure efficiently finds connected components (cycles).
  • For each connected cycle of size k (representing k couples that are interwoven), a minimum of k-1 swaps will arrange them correctly.
  • Alternative approaches using DFS/BFS or a greedy strategy are also viable.

Space and Time Complexity

Time Complexity: O(n) – We iterate once over the row and union-find operations are nearly constant time. Space Complexity: O(n) – Extra space for the union-find parent array and associated mapping structures.

Solution

We solve the problem by modeling the seating arrangement as a graph where each node represents a couple. We use union-find to combine nodes (couple groups) that are incorrectly paired in the seating arrangement. For every adjacent pair in the row, if the two persons belong to different couples, their corresponding groups are merged. Finally, each connected component (cycle) requiring k-1 swaps is counted to get the total number of swaps.

Code Solutions

# Python solution with comments

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row) // 2  # number of couples
        parent = [i for i in range(n)]  # union-find parent array initialization

        # Function to find root with path compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        # Union two groups if they are not already connected
        def union(x, y):
            rootX = find(x)
            rootY = find(y)
            if rootX != rootY:
                parent[rootX] = rootY

        # For each adjacent pair, union the corresponding couple groups
        for i in range(0, len(row), 2):
            couple1 = row[i] // 2
            couple2 = row[i+1] // 2
            union(couple1, couple2)

        # Count the size of each connected component
        groups = {}
        for i in range(n):
            root = find(i)
            groups[root] = groups.get(root, 0) + 1

        swaps = 0
        # For each group (cycle) of size k, need (k - 1) swaps
        for size in groups.values():
            swaps += size - 1

        return swaps

# End of Python solution
← Back to All Questions