Problem Description
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.
Key Insights
- Each couple consists of two consecutive integers (0 and 1, 2 and 3, etc.).
- The goal is to pair these integers by swapping elements in the array.
- The problem can be visualized as finding cycles in a mapping of current positions to target positions.
- Each cycle of length k requires (k - 1) swaps to arrange the elements correctly.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve this problem, we can use a greedy approach involving cycle detection. We first create a mapping of each person to their desired position based on their couple pair. Then, we iterate through the array to find cycles. For each cycle found, we calculate the number of swaps needed, which is (length of cycle - 1). We sum these swaps to get the total number of swaps required to arrange all couples side by side.