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.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`.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), iterating the seats for correction.
Space Complexity: O(N), necessary to track positions of individuals.
| 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. |
Don't Make This Coding Interview Mistake! | Jewels and Stones - Leetcode 771 • Greg Hogg • 443,129 views views
Watch 9 more video solutions →Practice Couples Holding Hands with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor