Leetcode #765: Couples Holding Hands

In this guide, we solve Leetcode #765 Couples Holding Hands in Python and focus on the core idea that makes the solution efficient.

You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.

Leetcode

Problem Statement

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.

Quick Facts

Difficulty: Hard
Premium: No
Tags: Greedy, Depth-First Search, Breadth-First Search, Union Find, Graph

Intuition

A locally optimal choice leads to a globally optimal result for this structure.

That means we can commit to decisions as we scan without backtracking.

Approach

Sort or preprocess if needed, then repeatedly take the best available local choice.

Maintain the minimal state necessary to validate the greedy decision.

Steps:

Sort or preprocess as needed.
Iterate and pick the best local option.
Track the current solution.

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

The time complexity is $O(n \times \alpha(n))$ , and the space complexity is $O(n)$ , where $\alpha(n)$ is the inverse Ackermann function, which can be considered a very small constant. The space complexity is $O(n)$ , where $\alpha(n)$ is the inverse Ackermann function, which can be considered a very small constant.

Edge Cases and Pitfalls

Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.

Summary

This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.

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

The time complexity is

O(n \times \alpha(n))

, and the space complexity is

O(n)

, where

\alpha(n)

is the inverse Ackermann function, which can be considered a very small constant. The space complexity is

O(n)

, where

\alpha(n)

is the inverse Ackermann function, which can be considered a very small constant.

Leetcode #765: Couples Holding Hands

Problem Statement

Quick Facts

Intuition

Approach

Example

Python Solution

Complexity

Edge Cases and Pitfalls

Summary

Ace your next coding interview

Leetcode #765: Couples Holding Hands

Problem Statement

Quick Facts

Intuition

Approach

Example

Python Solution

Complexity

Edge Cases and Pitfalls

Summary

Ace your next coding interview