HardNo. 0765
Couples Holding Hands — LeetCode 765 Python Solution
- Pattern
- Union-Find
- Topics
- Greedy, Depth-First Search, Breadth-First Search, Union Find, Graph
- Reading time
- 2 min
- Source
- leetcode.com
The problem
There are n couples sitting in 2n seats arranged in a row and want to hold hands. The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat.
Example
- Input
- row = [0,2,1,3]
- Output
- 1
- Explanation
- We only need to swap the second (row[1]) and third (row[2]) person.
Python solution
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(row) >> 1
p = list(range(n))
for i in range(0, len(row), 2):
a, b = row[i] >> 1, row[i + 1] >> 1
p[find(a)] = find(b)
return n - sum(i == find(i) for i in range(n))Complexity
- Time
- O(n × α(n))
- Space · auxiliary
- O(n), where α(n) is the inverse Ackermann function, which can be considered a very small constant
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 765. Couples Holding Hands is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1382 | Balance a Binary Search Tree | Medium |
| 2285 | Maximum Total Importance of Roads | Medium |
| 2497 | Maximum Star Sum of a Graph | Medium |
| 0768 | Max Chunks To Make Sorted II | Hard |
| 0769 | Max Chunks To Make Sorted | Medium |
| 0757 | Set Intersection Size At Least Two | Hard |
Frequently asked questions
- How hard is LeetCode 765. Couples Holding Hands?
LeetCode 765. Couples Holding Hands is rated Hard on LeetCode.
- What is the time complexity of LeetCode 765. Couples Holding Hands?
The Python solution on this page runs in O(n × α(n)).
- What is the space complexity of LeetCode 765. Couples Holding Hands?
The Python solution on this page uses O(n), where \alpha(n) is the inverse Ackermann function, which can be considered a very small constant auxiliary space.
- What topics does LeetCode 765. Couples Holding Hands cover?
LeetCode 765. Couples Holding Hands is tagged Greedy, Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.