LeetCode //C - 765. Couples Holding Hands

765. 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 i t h i^{th} 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.

From: LeetCode
Link: 765. Couples Holding Hands

Solution:

Ideas:

1. Iterate through pairs: Process seats in pairs (0-1, 2-3, 4-5, etc.)

2. Find partner: For each person, their partner is:

• If person ID is even: partner = person + 1
• If person ID is odd: partner = person - 1

3. Check if swap needed: If the two people in current seats are already a couple, continue to next pair

4. Find and swap: If not a couple, find where the partner of the first person is located and swap them with the second person

5. Count swaps: Increment the swap counter each time we perform a swap

Code:

int minSwapsCouples(int* row, int rowSize) { int swaps = 0; // Process each pair of seats for (int i = 0; i < rowSize; i += 2) { int person1 = row[i]; int person2 = row[i + 1]; // Find the partner of person1 // If person1 is even, partner is person1 + 1 // If person1 is odd, partner is person1 - 1 int partner1 = (person1 % 2 == 0) ? person1 + 1 : person1 - 1; // If person2 is already the partner of person1, continue if (person2 == partner1) { continue; } // Find where partner1 is located int partnerPos = -1; for (int j = i + 2; j < rowSize; j++) { if (row[j] == partner1) { partnerPos = j; break; } } // Swap person2 with partner1 row[i + 1] = partner1; row[partnerPos] = person2; swaps++; } return swaps;}