Couples Holding Hands - Solution & Explanation
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. 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 <= 30nis even.0 <= row[i] < 2n- All the elements of
roware unique.
Approach Overview
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 1: Union-Find Approach
This approach uses a Union-Find (also known as Disjoint Set Union, DSU) data structure to count the number of swaps needed to pair the couples. By treating each couple as a connected component, we can iterate through the row and connect each person to their designated partner. The number of swaps needed is equivalent to the number of components minus one.
The code defines a union-find or disjoint set structure to manage and connect couples efficiently. Each couple's pair is connected using the union operation inside a loop of couples. Finally, we check independent sets (or components) to compute the number of swaps, with the formula `swaps = components - 1`.
Complexity
Time Complexity: O(N), where N is the number of seats, because each union-find operation is O(1) on average using path compression and union by rank.
Space Complexity: O(N) for the parent array to store the parent of each node.
Approach 2: Greedy Approach with Cycle Counting
This approach processes the row greedily to minimize swaps by placing each person in its correct position. Misplaced pairs turn into cycles; reducing each cycle requires one swap for each element in excess of two in the cycle. Thus, we can directly count cycles and deduce swaps.
This C solution computes individual positions of persons to navigate swaps straightforwardly by positioning partners near one another. A systematic swap reduces cycles to achieve minimized swaps.
Complexity
Time Complexity: O(N), iterating the seats for correction.
Space Complexity: O(N), necessary to track positions of individuals.
Approach 3: Union-Find
We can assign a number to each pair of couples. Person with number 0 and 1 corresponds to couple 0, person with number 2 and 3 corresponds to couple 1, and so on. In other words, the person corresponding to row[i] has a couple number of \lfloor \frac{row[i]}{2} \rfloor.
If there are k pairs of couples who are seated incorrectly with respect to each other, i.e., if k pairs of couples are in the same permutation cycle, it will take k-1 swaps for all of them to be seated correctly.
Why? Consider the following: we first adjust the positions of a couple to their correct seats. After this, the problem reduces from k couples to k-1 couples. This process continues, and when k = 1, the number of swaps required is 0. Therefore, if k pairs of couples are in the wrong positions, we need k-1 swaps.
Thus, we only need to traverse the array once, use union-find to determine how many permutation cycles there are. Suppose there are x cycles, and the size of each cycle (in terms of couple pairs) is y_1, y_2, cdots, y_x. The number of swaps required is y_1-1 + y_2-1 + cdots + y_x-1 = y_1 + y_2 + cdots + y_x - x = n - x.
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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Union-Find Approach | Time Complexity: O(N), where N is the number of seats, because each union-find operation is O(1) on average using path compression and union by rank. |
| Greedy Approach with Cycle Counting | Time Complexity: O(N), iterating the seats for correction. |
| Union-Find | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode #765 couples holding hands | Java Solution • Arpan Pathak • 9,443 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Couples Holding Hands easy or hard?
How to solve Couples Holding Hands in O(n)?
What is the best approach for Couples Holding Hands?
Is Couples Holding Hands asked at Google/Amazon/Meta?
What data structure is used in Couples Holding Hands?
What is the time complexity of Couples Holding Hands?
Couples Holding Hands Python or Java solution approach?
Ready to solve this problem?
Practice Couples Holding Hands with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor