Couples Holding Hands

Hard

#0719Time: O(N^2), where N is the number of couples (i.e., `n` in the problem description, or `row.length / 2`). The outer loop runs N times. For each iteration, the inner linear search can take up to O(N) time in the worst case. This gives a total time complexity of O(N*N) = O(N^2).Space: O(1), as we only use a few variables to keep track of the swaps and loop indices. The swaps are performed in-place on the input array.1 company

Patterns

Greedy

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Graph

Companies

Citadel

Prompt

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^th 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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through the row, processing two seats at a time (a seat pair). For each seat pair, it ensures the two people sitting there form a couple. If they don't, it finds the correct partner for the first person in the pair by searching the rest of the row and then swaps them into the adjacent seat. This greedy choice is optimal because each swap resolves a seat pair permanently, reducing the problem to a smaller subproblem on the remaining seats.

Algorithm

Initialize a swaps counter to 0.
Iterate through the row array with a step of 2, from i = 0 to row.length - 2.
For each i, identify the person in the first seat of the pair, p1 = row[i].
Determine the required partner for p1, which is partner = p1 ^ 1 (using XOR is a concise way to find the partner, e.g., 0^1=1, 1^1=0, 2^1=3, 3^1=2).
Check if the person in the adjacent seat, row[i+1], is the partner.
If row[i+1] is not the partner, we need to find the partner and swap them into this seat.
- Increment the swaps counter.
- Perform a linear search for the partner in the rest of the array, starting from index i + 2.
- Once the partner is found at index j, swap the elements row[i+1] and row[j].
After the loop finishes, return the total swaps count.

Walkthrough

We iterate through the row array with a step of 2, focusing on seat pairs (i, i+1). For each i, we look at the person in seat i, let's call them p1 = row[i]. We determine their partner, partner = p1 ^ 1. We then check if the person in the adjacent seat, row[i+1], is the correct partner. If row[i+1] == partner, the couple is already together, and we move to the next pair of seats. If not, we must find the partner's current location. We perform a linear search for partner in the rest of the array (from index i+2 onwards). Once we find partner at index j, we swap the person at i+1 with the person at j. This action costs one swap. We increment our swap counter. After the swap, the pair at (i, i+1) is now a correct couple. We repeat this process for all seat pairs. The final count is the minimum number of swaps required.

1class Solution {2    public int minSwapsCouples(int[] row) {3        int swaps = 0;4        for (int i = 0; i < row.length; i += 2) {5            int p1 = row[i];6            int partner = p1 ^ 1;7            if (row[i + 1] != partner) {8                swaps++;9                for (int j = i + 2; j < row.length; j++) {10                    if (row[j] == partner) {11                        int temp = row[i + 1];12                        row[i + 1] = row[j];13                        row[j] = temp;14                        break;15                    }16                }17            }18        }19        return swaps;20    }21}

Complexity

Time

O(N^2), where N is the number of couples (i.e., `n` in the problem description, or `row.length / 2`). The outer loop runs N times. For each iteration, the inner linear search can take up to O(N) time in the worst case. This gives a total time complexity of O(N*N) = O(N^2).

Space

O(1), as we only use a few variables to keep track of the swaps and loop indices. The swaps are performed in-place on the input array.

Trade-offs

Pros

Simple to understand and implement.
It is a space-efficient solution, requiring only O(1) extra space.

Cons

The nested loop structure results in a quadratic time complexity, O(N^2), which is inefficient for large inputs. While the constraints of this problem are small, this approach would not scale well.

This approach is an optimization of the previous greedy strategy. The bottleneck in the first approach was the O(N) linear search to find the partner's location. We can eliminate this search by pre-processing the row array to store the index of each person in a hash map or, more efficiently, an array since the person IDs are contiguous. This allows us to find any person's location in O(1) time, bringing the overall time complexity down to linear.

Algorithm

First, create a position map, which can be an array pos of size 2n, to store the index of each person.
Iterate through the input row once to populate this map: pos[row[i]] = i.
Initialize a swaps counter to 0.
Iterate through the row array with a step of 2, from i = 0 to row.length - 2.
For each i, identify p1 = row[i] and their required partner = p1 ^ 1.
If row[i+1] is not the partner:
- Increment the swaps counter.
- Find the partner's current position in O(1) time using the map: partner_pos = pos[partner].
- Identify the person who is currently in the wrong seat: p2 = row[i+1].
- Perform the swap: row[i+1] becomes partner, and row[partner_pos] becomes p2.
- Crucially, update the position map to reflect the swap: pos[partner] is now i+1, and pos[p2] is now partner_pos.
Return the total swaps count.

Walkthrough

First, we create a mapping from each person's ID to their seat index. An array pos of size 2n is perfect for this, where pos[person_id] = seat_index. We populate this by iterating through the input row once. Then, we follow the same greedy strategy as before, iterating through seat pairs (i, i+1). For each i, we identify p1 = row[i] and their required partner = p1 ^ 1. If row[i+1] is not the partner, we need to perform a swap. Instead of searching, we directly look up the partner's position: partner_pos = pos[partner]. We also need to know who is currently sitting at i+1, let's say p2 = row[i+1]. We swap row[i+1] and row[partner_pos]. After swapping, we must update our pos array to reflect the new positions of p2 and partner. The partner is now at i+1, and p2 is now at partner_pos. We increment the swap counter and proceed to the next seat pair.

1class Solution {2    public int minSwapsCouples(int[] row) {3        int len = row.length;4        int[] pos = new int[len];5        for (int i = 0; i < len; i++) {6            pos[row[i]] = i;7        }8 9        int swaps = 0;10        for (int i = 0; i < len; i += 2) {11            int p1 = row[i];12            int partner = p1 ^ 1;13            if (row[i + 1] != partner) {14                swaps++;15                int partner_pos = pos[partner];16                int p2 = row[i + 1];17 18                // Swap in row array19                row[i + 1] = partner;20                row[partner_pos] = p2;21 22                // Update positions in pos array23                pos[partner] = i + 1;24                pos[p2] = partner_pos;25            }26        }27        return swaps;28    }29}

Complexity

Time

O(N), where N is the number of couples. Populating the `pos` array takes `O(2n)` time. The main loop runs `n` times, and all operations inside (lookups, swaps, and updates) are `O(1)`. The total time complexity is linear.

Space

O(N), where N is the number of couples. We use an auxiliary array `pos` of size `2n` to store the positions of each person.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Maintains the intuitive logic of the greedy approach while significantly improving performance.

Cons

Requires extra space proportional to the total number of people, which might be a concern for problems with very large n.

This approach models the problem from a graph-theoretic perspective. We can think of the n couples as n distinct nodes. The initial arrangement in the row array creates connections between these nodes. If a seat pair is occupied by people from two different couples, it means these two couples are 'tangled' together. We can use a Union-Find data structure to group these tangled couples into components. The key insight is that to untangle a component of k couples, it takes exactly k-1 swaps. Therefore, the total minimum number of swaps is n - (number of components).

Algorithm

The n couples (0,1), (2,3), ... are the entities we want to group. We can think of them as n nodes in a graph, indexed 0 to n-1.
Initialize a Union-Find (DSU) data structure with n elements, where each element initially forms its own set. The number of components is n.
Iterate through the n seat pairs. For each seat pair i (seats 2i and 2i+1):
- Get the people in these seats: p1 = row[2*i] and p2 = row[2*i+1].
- Determine the couple ID for each person. A person p belongs to couple p / 2.
- Let c1 = p1 / 2 and c2 = p2 / 2.
- These two couples, c1 and c2, are now linked because their members are sharing a seat pair. We merge their sets using the union(c1, c2) operation.
The union operation will merge the sets of c1 and c2 if they are not already in the same set, and in doing so, it decrements the total number of components.
After iterating through all seat pairs, the total number of swaps needed is n - (final number of components).

Walkthrough

We consider n nodes, where each node j represents the couple (2j, 2j+1). We initialize a Union-Find (DSU) data structure with n sets, one for each couple. The initial number of disjoint sets (components) is n. We then iterate through the n seat pairs. For each seat pair i (seats 2i and 2i+1), we look at the two people sitting there, p1 = row[2i] and p2 = row[2i+1]. We determine which couple each person belongs to: person p belongs to couple p/2. So, p1 belongs to couple c1 = p1/2, and p2 belongs to couple c2 = p2/2. The fact that members of couple c1 and c2 are in the same seat pair implies a dependency. We represent this by merging the sets containing c1 and c2 using the union operation. If c1 and c2 were already in the same set, the union operation does nothing. If they were in different sets, they are merged, and the total number of components decreases by one. After iterating through all n seat pairs, the total number of swaps is n - (total number of components).

1class DSU {2    private int[] parent;3    private int count;4 5    public DSU(int n) {6        parent = new int[n];7        count = n;8        for (int i = 0; i < n; i++) {9            parent[i] = i;10        }11    }12 13    public int find(int i) {14        if (parent[i] == i) {15            return i;16        }17        return parent[i] = find(parent[i]); // Path compression18    }19 20    public void union(int i, int j) {21        int rootI = find(i);22        int rootJ = find(j);23        if (rootI != rootJ) {24            parent[rootI] = rootJ;25            count--;26        }27    }28 29    public int getCount() {30        return count;31    }32}33 34class Solution {35    public int minSwapsCouples(int[] row) {36        int n_couples = row.length / 2;37        DSU dsu = new DSU(n_couples);38 39        for (int i = 0; i < row.length; i += 2) {40            int couple1 = row[i] / 2;41            int couple2 = row[i + 1] / 2;42            dsu.union(couple1, couple2);43        }44 45        return n_couples - dsu.getCount();46    }47}

Complexity

Time

O(N * α(N)), where N is the number of couples and α is the extremely slow-growing Inverse Ackermann function. The loop runs N times, and with path compression and union by rank/size, each `union` operation takes nearly constant amortized time. For all practical purposes, this is considered linear time, O(N).

Space

O(N), where N is the number of couples. This space is used to store the `parent` array (and potentially a `rank` or `size` array) for the DSU data structure.

Trade-offs

Pros

Provides an elegant and highly efficient solution.
Asymptotically one of the fastest known solutions for this type of problem.
Offers a powerful, abstract way to reason about connectivity and cycles.

Cons

The concept of Union-Find is more abstract and might be less intuitive than a direct greedy approach.
Requires implementing or using a DSU data structure, which adds a bit of overhead compared to a simple array-based greedy solution.

Solutions

Solution

1public class Solution {2    private int[] p;3    public int MinSwapsCouples(int[] row) {4        int n = row.Length >> 1;5        p = new int[n];6        for (int i = 0; i < n; ++i) {7            p[i] = i;8        }9        for (int i = 0; i < n << 1; i += 2) {10            int a = row[i] >> 1;11            int b = row[i + 1] >> 1;12            p[find(a)] = find(b);13        }14        int ans = n;15        for (int i = 0; i < n; ++i) {16            if (p[i] == i) {17                --ans;18            }19        }20        return ans;21    }22    private int find(int x) {23        if (p[x] != x) {24            p[x] = find(p[x]);25        }26        return p[x];27    }28}

1class Solution {2private3  int[] p;4public5  int minSwapsCouples(int[] row) {6    int n = row.length >> 1;7    p = new int[n];8    for (int i = 0; i < n; ++i) {9      p[i] = i;10    }11    for (int i = 0; i < n << 1; i += 2) {12      int a = row[i] >> 1, b = row[i + 1] >> 1;13      p[find(a)] = find(b);14    }15    int ans = n;16    for (int i = 0; i < n; ++i) {17      if (i == find(i)) {18        --ans;19      }20    }21    return ans;22  }23private24  int find(int x) {25    if (p[x] != x) {26      p[x] = find(p[x]);27    }28    return p[x];29  }30}

1class Solution {2public:3  int minSwapsCouples(vector<int> &row) {4    int n = row.size() / 2;5    int p[n];6    iota(p, p + n, 0);7    function<int(int)> find = [&](int x) -> int {8      if (p[x] != x) {9        p[x] = find(p[x]);10      }11      return p[x];12    };13    for (int i = 0; i < n << 1; i += 2) {14      int a = row[i] >> 1, b = row[i + 1] >> 1;15      p[find(a)] = find(b);16    }17    int ans = n;18    for (int i = 0; i < n; ++i) {19      ans -= i == find(i);20    }21    return ans;22  }23};

1class Solution:2    def minSwapsCouples(self, row: List[int]) -> int: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] n = len(row) >> 1 p = list(range(n)) for i in range(0, len(row), 2): a, b = row[i] >> 1, row[i + 1] >> 1 p[find(a)] = find(b) return n - sum(i == find(i) for i in range(n))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution {2    private int[] p;3    public int MinSwapsCouples(int[] row) {4        int n = row.Length >> 1;5        p = new int[n];6        for (int i = 0; i < n; ++i) {7            p[i] = i;8        }9        for (int i = 0; i < n << 1; i += 2) {10            int a = row[i] >> 1;11            int b = row[i + 1] >> 1;12            p[find(a)] = find(b);13        }14        int ans = n;15        for (int i = 0; i < n; ++i) {16            if (p[i] == i) {17                --ans;18            }19        }20        return ans;21    }22    private int find(int x) {23        if (p[x] != x) {24            p[x] = find(p[x]);25        }26        return p[x];27    }28}

1class Solution {2private3  int[] p;4public5  int minSwapsCouples(int[] row) {6    int n = row.length >> 1;7    p = new int[n];8    for (int i = 0; i < n; ++i) {9      p[i] = i;10    }11    for (int i = 0; i < n << 1; i += 2) {12      int a = row[i] >> 1, b = row[i + 1] >> 1;13      p[find(a)] = find(b);14    }15    int ans = n;16    for (int i = 0; i < n; ++i) {17      if (i == find(i)) {18        --ans;19      }20    }21    return ans;22  }23private24  int find(int x) {25    if (p[x] != x) {26      p[x] = find(p[x]);27    }28    return p[x];29  }30}

1class Solution {2public:3  int minSwapsCouples(vector<int> &row) {4    int n = row.size() / 2;5    int p[n];6    iota(p, p + n, 0);7    function<int(int)> find = [&](int x) -> int {8      if (p[x] != x) {9        p[x] = find(p[x]);10      }11      return p[x];12    };13    for (int i = 0; i < n << 1; i += 2) {14      int a = row[i] >> 1, b = row[i + 1] >> 1;15      p[find(a)] = find(b);16    }17    int ans = n;18    for (int i = 0; i < n; ++i) {19      ans -= i == find(i);20    }21    return ans;22  }23};

1class Solution:2    def minSwapsCouples(self, row: List[int]) -> int: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] n = len(row) >> 1 p = list(range(n)) for i in range(0, len(row), 2): a, b = row[i] >> 1, row[i + 1] >> 1 p[find(a)] = find(b) return n - sum(i == find(i) for i in range(n))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.