How do you solve Couples Holding Hands on LeetCode?

Couples Holding Hands (LeetCode #765) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Couples can be represented as pairs, and finding swaps can be thought of as connecting nodes in a graph.

What is the brute force solution for Couples Holding Hands?

The brute force approach for Couples Holding Hands is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves trying every possible pair of swaps to see if we can arrange the couples next to each other. This is simple but inefficient, as it may require checking many combinations. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Couples Holding Hands?

Always clarify the problem and constraints before diving into a solution. Think about edge cases, such as when couples are already sitting together. Explain your thought process clearly while coding, as it shows your understanding.

What are common mistakes when solving Couples Holding Hands?

Not considering that multiple swaps can be needed to bring couples together. Failing to recognize that the problem can be modeled as a graph.

#765

Couples Holding Hands

Hard

GreedyDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryUnion-FindGraph Theory

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a greedy approach with a Union-Find data structure to efficiently group couples and count the minimum swaps needed. This is much faster than brute force because it avoids unnecessary checks.

⚙️

Algorithm

3 steps

1Step 1: Create a Union-Find structure to represent the couples.
2Step 2: Iterate through the row and union each person with their partner based on their indices.
3Step 3: Count the number of unique groups formed and calculate the number of swaps needed based on the number of groups.

solution.py18 lines

1class UnionFind:
2    def __init__(self, n):
3        self.parent = list(range(n))
4    def find(self, x):
5        if self.parent[x] != x:
6            self.parent[x] = self.find(self.parent[x])
7        return self.parent[x]
8    def union(self, x, y):
9        self.parent[self.find(x)] = self.find(y)
10
11def minSwapsCouples(row):
12    n = len(row) // 2
13    uf = UnionFind(n)
14    for i in range(len(row)):
15        partner = row[i] // 2
16        uf.union(i // 2, partner)
17    groups = len(set(uf.find(i) for i in range(n)))
18    return n - groups

ℹ

Complexity note: The time complexity is O(n) because we perform a constant amount of work for each person in the row, and the space complexity is O(n) due to the Union-Find structure.

1Couples can be represented as pairs, and finding swaps can be thought of as connecting nodes in a graph.
2Using Union-Find allows us to efficiently manage and group connected components.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.