The Question
Coding

Couples Holding Hands

There are $n$ couples sitting in $2n$ seats arranged in a row. The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the $i$-th seat. The couples are defined by their IDs: the first couple is $(0, 1)$, the second couple is $(2, 3)$, and so on, with the last couple being $(2n - 2, 2n - 1)$. You want to rearrange the people so that every couple is sitting side by side (i.e., in seats $(0, 1), (2, 3), \dots$). A single swap consists of choosing any two people currently in seats and having them switch places. Return the minimum number of swaps required to achieve this state. Constraints: - 2n == row.length - 2 <= n <= 30 - row is a permutation of [0, 2n - 1].
Java
Greedy
Union-Find
Questions & Insights

Clarifying Questions

What is the maximum value of n (the number of couples)?
Are we guaranteed that the input array row will always have an even length and contain a permutation of integers from 0 to 2n-1?
Does the order within the pair matter? (e.g., is [0, 1] the same as [1, 0])?
Can we perform swaps between any two positions in the array, or only adjacent ones?

Assumptions

n is relatively small (e.g., up to 30-50), allowing for O(n^2) or O(n) solutions.
The input is a valid permutation of 0 \dots 2n-1.
Any two people can be swapped regardless of their current distance.
The order within a pair does not matter; as long as 2k and 2k+1 are adjacent, the condition is met.

Thinking Process

Cycle Decomposition Intuition: This problem can be modeled as a graph problem. Each pair of seats (2i, 2i+1) is a "couch." If a couch contains person And person B who are not partners, it means A's partner is on another couch, and B's partner is on yet another. This creates a chain or cycle of dependencies.
Greedy Strategy: We can iterate through the array couch by couch (indices 0, 2, 4, \dots). For each person at index i, their partner must be row[i] ^ 1. If the person already sitting at i+1 is not the partner, we find where the partner is sitting and swap them into i+1.
Why Greedy Works: Swapping the correct partner into the current couch is always optimal because it satisfies one couch's requirement immediately and doesn't disrupt any couches we've already fixed. This is equivalent to reducing the number of components in a graph.
Efficient Lookup: To avoid O(n) searching for the partner in every step, we can maintain an auxiliary array (or HashMap) pos where pos[person_id] stores the current index of that person in the row array.
Implementation Breakdown

Problem Set

Functional Requirement: Return the minimum number of swaps to pair all couples.
Constraints:
row.length == 2 * n
2 <= n <= 30
row is a permutation of [0, 2n - 1].

Approach

Algorithm: Greedy with Position Map.
Data Structure: Integer Array for position indexing.
Complexity:
Time: O(n), where n is the number of couples (we iterate through the array once).
Space: O(n) to store the positions of each person.

Implementation

Wrap Up

Advanced Topics

Union-Find Approach: One could also solve this by counting connected components. If n is the number of couples and C is the number of connected components in the graph where nodes are couples and edges exist if a couch contains members from two different couples, the answer is n - C.
Parallelization: In a massive seating arrangement, we could identify independent cycles and process them in parallel.
Readability vs. Performance: While the XOR bitwise operator ^ 1 is highly efficient and standard for this problem, in a real-world enterprise codebase, a helper method getPartner(int id) might be preferred for clarity.