Watch 10 video solutions for Couples Holding Hands, a hard level problem involving Greedy, Depth-First Search, Breadth-First Search. This walkthrough by Arpan Pathak has 9,264 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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. 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.length2 <= n <= 30n is even.0 <= row[i] < 2nrow are unique.Problem Overview: You are given a row of seats where people are labeled from 0 to 2n-1. Every pair (0,1), (2,3), (4,5) forms a couple. The task is to compute the minimum number of swaps needed so every couple sits together.
Approach 1: Greedy with Cycle Counting (O(n) time, O(1) space)
The key observation is that each person has exactly one partner: x ^ 1 gives the partner of x. Iterate through the row in steps of two because seats are paired. For each pair, check whether the second seat contains the correct partner. If not, locate the partner later in the array and swap it into position. A hash map or index array helps track positions so the swap happens in constant time. Each swap fixes one couple, so the total number of swaps corresponds to the number of misplaced partners. This greedy strategy works because fixing the current pair never harms already-correct pairs.
Approach 2: Union-Find / Connected Components (O(n) time, O(n) space)
Model the problem as a graph problem where each couple represents a node. For every seat pair, connect the couples of the two people sitting there. If two members of different couples share a seat pair, their couples belong to the same connected component. Using a Union Find structure, union the couples appearing together in each seat pair. If a component contains k couples, it requires k - 1 swaps to arrange them correctly. Summing this across all components gives the minimum swaps. This interpretation converts the seating constraints into a connected component problem on a graph.
The greedy method relies on direct swaps and position tracking, while the union-find solution groups couples based on conflicts. Both approaches run in linear time because each seat pair is processed once.
Recommended for interviews: The greedy swap approach is usually expected because it is simple and runs in O(n) time with constant extra space. The union-find solution demonstrates strong understanding of greedy reasoning and graph connectivity. Showing the greedy idea first and mentioning the union-find interpretation signals strong problem-solving depth.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Swap with Cycle Counting | O(n) | O(1) | Best for interviews and production code when you can track partner positions and perform direct swaps |
| Union-Find (Connected Components) | O(n) | O(n) | Useful when modeling the seating as a graph problem or when explaining the theoretical structure of conflicts |