Couples Holding Hands solution and explanation
Google
9 more videos on this problem
Leetcode #765 couples holding hands | Java SolutionArpan Pathak · 9:54 · 9K views
LeetCode 765. Couples Holding Hands Explanation and Solutionhappygirlzt · 8:31 · 7K views
765. Couples Holding Hands (Leetcode Hard)Programming Live with Larry · 40:20 · 2K views
Leetcode 765. Couples Holding Hands (union find)LetsCode · 14:45 · 1K views
Leetcode 765. Couples Holding Hands | Union Find | Graph TheoryJeezy Leets · 24:32 · 1K views
Couples Holding Hands. [LeetCode]Noah Sealy · 3:58 · 1K views
【每日一题】765. Couples Holding Hands, 10/11/2019Huifeng Guan · 27:08 · 1K views
LeetCode 765: Couples Holding Hands | Minimum Swaps | Hindi ExplanationCode Kage · 10:34 · 598 views
765. Couples Holding Hands 情侣牵手【LeetCode 力扣官方题解】LeetCode 力扣 · 6:55 · 498 views
Solving a Hard LeetCode Problem (Couples Holding Hands) | Unscripted CodingUnscripted Coding · 51:44 · 479 views
The problem
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 <= 30nis even.0 <= row[i] < 2n- All the elements of
roware unique.
Approach overview
Problem Overview: You are given a row of seats where people are labeled from 0 to 2n-1. Every pair (0,1), (2,3), (4,5) forms a couple. The task is to compute the minimum number of swaps needed so every couple sits together.
Approach 1: Greedy with Cycle Counting (O(n) time, O(1) space)
The key observation is that each person has exactly one partner: x ^ 1 gives the partner of x. Iterate through the row in steps of two because seats are paired. For each pair, check whether the second seat contains the correct partner. If not, locate the partner later in the array and swap it into position. A hash map or index array helps track positions so the swap happens in constant time. Each swap fixes one couple, so the total number of swaps corresponds to the number of misplaced partners. This greedy strategy works because fixing the current pair never harms already-correct pairs.
Approach 2: Union-Find / Connected Components (O(n) time, O(n) space)
Model the problem as a graph problem where each couple represents a node. For every seat pair, connect the couples of the two people sitting there. If two members of different couples share a seat pair, their couples belong to the same connected component. Using a Union Find structure, union the couples appearing together in each seat pair. If a component contains k couples, it requires k - 1 swaps to arrange them correctly. Summing this across all components gives the minimum swaps. This interpretation converts the seating constraints into a connected component problem on a graph.
The greedy method relies on direct swaps and position tracking, while the union-find solution groups couples based on conflicts. Both approaches run in linear time because each seat pair is processed once.
Recommended for interviews: The greedy swap approach is usually expected because it is simple and runs in O(n) time with constant extra space. The union-find solution demonstrates strong understanding of greedy reasoning and graph connectivity. Showing the greedy idea first and mentioning the union-find interpretation signals strong problem-solving depth.
Approach 1: Union-Find Approach
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.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.parent[rootX] = rootY
class Solution:
def minSwapsCouples(self, row):
n = len(row) // 2
uf = UnionFind(n)
for i in range(0, len(row), 2):
a, b = row[i] // 2, row[i + 1] // 2
uf.union(a, b)
return sum(1 for i in range(n) if uf.find(i) == i) - 1
row = [0, 2, 1, 3]
sol = Solution()
print(f"Minimum swaps required: {sol.minSwapsCouples(row)}")import java.util.*;
class Solution {
static class UnionFind {
int[] parent;
UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}
public int minSwapsCouples(int[] row) {
int n = row.length / 2;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < row.length; i += 2) {
int a = row[i];
int b = row[i + 1];
uf.union(a / 2, b / 2);
}
int swaps = 0;
for (int i = 0; i < n; i++) {
if (uf.find(i) == i) swaps++;
}
return swaps - 1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] row = {0, 2, 1, 3};
System.out.println("Minimum swaps required: " + sol.minSwapsCouples(row));
}
}#include <vector>
#include <iostream>
using namespace std;
class UnionFind {
private:
vector<int> parent;
public:
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
};
int minSwapsCouples(vector<int>& row) {
int n = row.size() / 2;
UnionFind uf(n);
for (int i = 0; i < row.size(); i += 2) {
int a = row[i], b = row[i + 1];
uf.unite(a / 2, b / 2);
}
int swaps = n;
for (int i = 0; i < n; ++i) {
if (uf.find(i) == i) swaps--;
}
return swaps;
}
int main() {
vector<int> row = {0, 2, 1, 3};
cout << "Minimum swaps required: " << minSwapsCouples(row) << endl;
return 0;
}class UnionFind {
constructor(size) {
this.parent = Array.from({ length: size }, (_, i) => i);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
this.parent[rootX] = rootY;
}
}
}
function minSwapsCouples(row) {
const n = row.length / 2;
const uf = new UnionFind(n);
for (let i = 0; i < row.length; i += 2) {
const a = Math.floor(row[i] / 2);
const b = Math.floor(row[i + 1] / 2);
uf.union(a, b);
}
let swaps = 0;
for (let i = 0; i < n; i++) {
if (uf.find(i) === i) swaps++;
}
return swaps - 1;
}
const row = [0, 2, 1, 3];
console.log(`Minimum swaps required: ${minSwapsCouples(row)}`);#include <stdio.h>
#define MAXN 60
int parent[MAXN];
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) parent[rootX] = rootY;
}
int minSwapsCouples(int* row, int rowSize) {
for (int i = 0; i < rowSize; i++) {
parent[i] = i;
}
for (int i = 0; i < rowSize; i += 2) {
int a = row[i];
int b = row[i + 1];
unionSet(a / 2, b / 2);
}
int swaps = 0;
for (int i = 0; i < rowSize / 2; ++i) {
if (find(i) == i) swaps++;
}
return swaps - 1;
}
int main() {
int row[] = {0, 2, 1, 3};
int size = sizeof(row)/sizeof(row[0]);
printf("Minimum swaps required: %d", minSwapsCouples(row, size));
return 0;
}using System;
public class UnionFind {
private int[] parent;
public UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}
public class Solution {
public int MinSwapsCouples(int[] row) {
int n = row.Length / 2;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < row.Length; i += 2) {
int a = row[i] / 2, b = row[i + 1] / 2;
uf.Union(a, b);
}
int swaps = 0;
for (int i = 0; i < n; i++) {
if (uf.Find(i) == i) swaps++;
}
return swaps - 1;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] row = {0, 2, 1, 3};
Console.WriteLine("Minimum swaps required: " + sol.MinSwapsCouples(row));
}
}The Python solution applies Union-Find to group together people who should be seated as couples. By finding the number of disjoint sets after processing the union operations, it derives the minimum number of swaps required to correctly seat all couples side by side.
Time Complexity: O(N), as each operation in the union-find is quasi-linear due to path compression.
Space Complexity: O(N), for the parent array within the union-find structure.
Approach 2: Greedy Approach with Cycle Counting
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.
class Solution:
def minSwapsCouples(self, row):
n = len(row)
pos = {x: i for i, x in enumerate(row)}
swaps = 0
for i in range(0, n, 2):
partner = row[i] ^ 1
if row[i + 1] != partner:
swaps += 1
swapWith = pos[partner]
pos[row[i + 1]] = swapWith
row[i + 1], row[swapWith] = row[swapWith], row[i + 1]
return swaps
row = [0, 2, 1, 3]
sol = Solution()
print(f"Minimum swaps required: {sol.minSwapsCouples(row)}")public class Solution {
public int minSwapsCouples(int[] row) {
int n = row.length;
int[] pos = new int[n];
for (int i = 0; i < n; i++) {
pos[row[i]] = i;
}
int swaps = 0;
for (int i = 0; i < n; i += 2) {
int partner = row[i] ^ 1;
if (row[i + 1] != partner) {
swaps++;
int swapWith = pos[partner];
pos[row[i + 1]] = swapWith;
int temp = row[i + 1];
row[i + 1] = row[swapWith];
row[swapWith] = temp;
}
}
return swaps;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] row = {0, 2, 1, 3};
System.out.println("Minimum swaps required: " + sol.minSwapsCouples(row));
}
}#include <vector>
#include <iostream>
using namespace std;
int minSwapsCouples(vector<int>& row) {
int n = row.size();
vector<int> pos(n);
for (int i = 0; i < n; ++i) {
pos[row[i]] = i;
}
int swaps = 0;
for (int i = 0; i < n; i += 2) {
int partner = row[i] ^ 1;
if (row[i + 1] != partner) {
++swaps;
int swapWith = pos[partner];
pos[row[i + 1]] = swapWith;
swap(row[i + 1], row[swapWith]);
}
}
return swaps;
}
int main() {
vector<int> row = {0, 2, 1, 3};
cout << "Minimum swaps required: " << minSwapsCouples(row) << endl;
return 0;
}function minSwapsCouples(row) {
const n = row.length;
const pos = Array(n).fill(0);
for (let i = 0; i < n; i++) {
pos[row[i]] = i;
}
let swaps = 0;
for (let i = 0; i < n; i += 2) {
const partner = row[i] ^ 1;
if (row[i + 1] !== partner) {
swaps++;
const swapWith = pos[partner];
pos[row[i + 1]] = swapWith;
[row[i + 1], row[swapWith]] = [row[swapWith], row[i + 1]];
}
}
return swaps;
}
const row = [0, 2, 1, 3];
console.log(`Minimum swaps required: ${minSwapsCouples(row)}`);#include <stdio.h>
#include <stdbool.h>
int minSwapsCouples(int* row, int rowSize) {
int pos[rowSize];
for (int i = 0; i < rowSize; i++) {
pos[row[i]] = i;
}
int swaps = 0;
for (int i = 0; i < rowSize; i += 2) {
int partner = row[i] ^ 1;
if (row[i+1] != partner) {
swaps++;
int swapWith = pos[partner];
pos[row[i+1]] = swapWith;
int temp = row[i+1];
row[i+1] = row[swapWith];
row[swapWith] = temp;
}
}
return swaps;
}
int main() {
int row[] = {0, 2, 1, 3};
int size = sizeof(row) / sizeof(row[0]);
printf("Minimum swaps required: %d", minSwapsCouples(row, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinSwapsCouples(int[] row) {
int n = row.Length;
int[] pos = new int[n];
for (int i = 0; i < n; i++) {
pos[row[i]] = i;
}
int swaps = 0;
for (int i = 0; i < n; i += 2) {
int partner = row[i] ^ 1;
if (row[i + 1] != partner) {
swaps++;
int swapWith = pos[partner];
pos[row[i + 1]] = swapWith;
int temp = row[i + 1];
row[i + 1] = row[swapWith];
row[swapWith] = temp;
}
}
return swaps;
}
public static void Main(string[] args) {
int[] row = {0, 2, 1, 3};
Solution sol = new Solution();
Console.WriteLine("Minimum swaps required: " + sol.MinSwapsCouples(row));
}
}The Python solution employs a hash table for position tracking, which pairs each individual optimally, performing swaps with their partners through logical exercises to reduce misplaced seats.
Time Complexity: O(N), carefully reformatted for half the row size.
Space Complexity: O(N), managing partner positioning.
Approach 3: Union-Find
We can assign a number to each pair of couples. Person with number 0 and 1 corresponds to couple 0, person with number 2 and 3 corresponds to couple 1, and so on. In other words, the person corresponding to row[i] has a couple number of \lfloor \frac{row[i]}{2} \rfloor.
If there are k pairs of couples who are seated incorrectly with respect to each other, i.e., if k pairs of couples are in the same permutation cycle, it will take k-1 swaps for all of them to be seated correctly.
Why? Consider the following: we first adjust the positions of a couple to their correct seats. After this, the problem reduces from k couples to k-1 couples. This process continues, and when k = 1, the number of swaps required is 0. Therefore, if k pairs of couples are in the wrong positions, we need k-1 swaps.
Thus, we only need to traverse the array once, use union-find to determine how many permutation cycles there are. Suppose there are x cycles, and the size of each cycle (in terms of couple pairs) is y_1, y_2, cdots, y_x. The number of swaps required is y_1-1 + y_2-1 + cdots + y_x-1 = y_1 + y_2 + cdots + y_x - x = n - x.
The time complexity is O(n times \alpha(n)), and the space complexity is O(n), where \alpha(n) is the inverse Ackermann function, which can be considered a very small constant.
function minSwapsCouples(row: number[]): number {
const n = row.length >> 1;
const p: number[] = Array(n)
.fill(0)
.map((_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
for (let i = 0; i < n << 1; i += 2) {
const a = row[i] >> 1;
const b = row[i + 1] >> 1;
p[find(a)] = find(b);
}
let ans = n;
for (let i = 0; i < n; ++i) {
if (i === find(i)) {
--ans;
}
}
return ans;
}func minSwapsCouples(row []int) int {
n := len(row) >> 1
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for i := 0; i < n<<1; i += 2 {
a, b := row[i]>>1, row[i+1]>>1
p[find(a)] = find(b)
}
ans := n
for i := range p {
if find(i) == i {
ans--
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Union-Find Approach | Time Complexity: O(N), as each operation in the union-find is quasi-linear due to path compression. |
| Greedy Approach with Cycle Counting | Time Complexity: O(N), carefully reformatted for half the row size. |
| Union-Find | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Swap with Cycle Counting | O(n) | O(1) | Best for interviews and production code when you can track partner positions and perform direct swaps |
| Union-Find (Connected Components) | O(n) | O(n) | Useful when modeling the seating as a graph problem or when explaining the theoretical structure of conflicts |
Frequently asked questions
Is Couples Holding Hands easy or hard?
Couples Holding Hands is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the hidden structure of cycles or connected components rather than the implementation itself. Once the greedy or union-find insight is clear, the code becomes straightforward.
How to solve Couples Holding Hands in O(n)?
Process the row two seats at a time. For each person x, compute their partner using x ^ 1. If the adjacent seat does not contain the partner, find the partner’s current index and swap them into position while updating the index map. Each swap fixes one pair, so the algorithm completes in linear time.
What is the best approach for Couples Holding Hands?
The greedy swap approach is typically the best solution. Iterate through seat pairs and ensure each person sits with their partner using direct swaps tracked with an index map. This runs in O(n) time with O(1) extra space and is usually the approach expected in coding interviews.
Is Couples Holding Hands asked at Google/Amazon/Meta?
Couples Holding Hands appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests greedy reasoning, graph modeling, and union-find techniques. Interviewers use it to evaluate whether candidates can transform a seating problem into cycles or connected components.
What data structure is used in Couples Holding Hands?
Common data structures include arrays for tracking positions and the Union-Find (Disjoint Set Union) structure for grouping couples into connected components. The greedy approach relies mainly on index mapping and swapping operations.
What is the time complexity of Couples Holding Hands?
Both optimal approaches run in O(n) time where n is the number of seats. Each seat pair is processed once. The greedy method uses constant extra space, while the union-find approach requires O(n) space to maintain parent arrays for connected components.
Couples Holding Hands Python or Java solution approach?
Python and Java implementations usually follow the greedy swap strategy. Maintain an index map from person to seat, iterate through pairs, compute the partner using x ^ 1, and swap when necessary. The logic remains identical across languages and runs in O(n) time.