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 \times \alpha(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.

Couples Holding Hands — LeetCode 765 Python Solution

HardGreedyDepth-First SearchBreadth-First SearchUnion FindGraph

Problem: #765
Pattern: Union-Find
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

Python

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

Measure	Complexity
Time	O(n \times \alpha(n))
Space	O(n), where \alpha(n) is the inverse Ackermann function, which can be considered a very small constant auxiliary

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.

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 \times \alpha(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.