{x}
blog image

Couples Holding Hands

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.length
  • 2 <= n <= 30
  • n is even.
  • 0 <= row[i] < 2n
  • All the elements of row are unique.

Solution Explanation:

This problem can be efficiently solved using Union-Find. The core idea is to represent couples as connected components in a disjoint-set data structure. Each person is assigned an index representing their half of a couple (e.g., couple (0,1) has person 0 and person 1; index 0 represents both of them). Initially, each person is in its own set. Then, we iterate through the row array, identifying pairs of seated people. If they belong to the same couple (indices are the same after integer division by 2), we don't need to do anything. If they belong to different couples, we unite their sets.

Finally, the number of swaps needed equals the number of connected components minus 1 (since each connected component represents a group of couples that need to be swapped into the correct arrangement).

Algorithm:

  1. Initialization: Create a parent array p of size n (where 2n is the length of the row array), representing the disjoint sets. Initially, each element p[i] = i. find(x) function is used to find the root of the set containing x.

  2. Union: Iterate through row in pairs. For each pair (row[i], row[i+1]), find the indices a and b representing the halves of the couples they belong to (using integer division by 2). Use the find() function to find the root of the sets a and b belong to. If the roots are different, unite the sets using p[find(a)] = find(b).

  3. Counting Components: After processing all pairs, count the number of sets (connected components) by counting how many indices i satisfy p[i] == i. This count represents the number of independent groups of couples.

  4. Result: The minimum number of swaps is n (the number of couples) minus the number of connected components.

Time Complexity Analysis

  • Initialization: O(n) to initialize the parent array p.
  • Union: O(n) to iterate through the array and perform union operations. The amortized time complexity of the union operation in Union-Find is close to O(1) using path compression and union by rank (although not explicitly implemented in all code examples above).
  • Counting Components: O(n) to iterate through the array and count the number of components.

Therefore, the overall time complexity is O(n), linear in the number of couples.

Space Complexity Analysis

The space complexity is dominated by the p array, which has size n. Thus, the space complexity is O(n).

Code Examples (with detailed comments):

The provided code examples in Python, Java, C++, Go, TypeScript, and C# all implement this Union-Find algorithm efficiently. The find() function efficiently locates the root of a set using path compression (although some versions don't explicitly implement union by rank for better optimization). The core logic remains consistent across all languages. Refer to the inline comments in the provided code for more specific explanations within each language's context.