Is Couples Holding Hands easy or hard?

Couples Holding Hands is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the hidden structure of cycles or connected components rather than the implementation itself. Once the greedy or union-find insight is clear, the code becomes straightforward.

How to solve Couples Holding Hands in O(n)?

Process the row two seats at a time. For each person x, compute their partner using x ^ 1. If the adjacent seat does not contain the partner, find the partner’s current index and swap them into position while updating the index map. Each swap fixes one pair, so the algorithm completes in linear time.

What is the best approach for Couples Holding Hands?

The greedy swap approach is typically the best solution. Iterate through seat pairs and ensure each person sits with their partner using direct swaps tracked with an index map. This runs in O(n) time with O(1) extra space and is usually the approach expected in coding interviews.

Is Couples Holding Hands asked at Google/Amazon/Meta?

Couples Holding Hands appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests greedy reasoning, graph modeling, and union-find techniques. Interviewers use it to evaluate whether candidates can transform a seating problem into cycles or connected components.

What data structure is used in Couples Holding Hands?

Common data structures include arrays for tracking positions and the Union-Find (Disjoint Set Union) structure for grouping couples into connected components. The greedy approach relies mainly on index mapping and swapping operations.

What is the time complexity of Couples Holding Hands?

Both optimal approaches run in O(n) time where n is the number of seats. Each seat pair is processed once. The greedy method uses constant extra space, while the union-find approach requires O(n) space to maintain parent arrays for connected components.

Couples Holding Hands Python or Java solution approach?

Python and Java implementations usually follow the greedy swap strategy. Maintain an index map from person to seat, iterate through pairs, compute the partner using x ^ 1, and swap when necessary. The logic remains identical across languages and runs in O(n) time.

Description Hints 1 Solution Video 9:54

765. Couples Holding Hands

Hard59.8% acceptance5 companies

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 i^th seat. The couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2n - 2, 2n - 1).

Return the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

Example 1:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3,2,0,1]
Output: 0
Explanation: All couples are already seated side by side.

Constraints:

2n == row.length
2 <= n <= 30
n is even.
0 <= row[i] < 2n
All the elements of row are unique.

Asked at 5 companies

Citadel Squarepoint Capital

Google Microsoft Bloomberg

Topics

Hints open one at a time

Hint 1

Say there are N two-seat couches. For each couple, draw an edge from the couch of one partner to the couch of the other partner.

9:54

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution