Couples Holding Hands — Solution in Python, Java & C++
Couples Holding Hands solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on greedy and graph.
Couples Holding Hands is a hard coding problem on greedy, graph and union find, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Greedy, Graph, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
At the CodeKairo awards dinner, n couples sit in a row of 2n seats. row[i] is the id of the person in seat i. Couples are numbered in order: person 0 is paired with 1, 2 with 3, and in general 2k with 2k + 1.
A swap picks any two people and exchanges their seats. Return the minimum number of swaps so that every couple sits side by side, meaning seats 2i and 2i + 1 hold a couple for every i.
Example 1
Input: row = [0,2,1,3]
Output: 1
Explanation: Swap the people in seats 1 and 2.
Example 2
Input: row = [3,2,0,1]
Output: 0
Example 3
Input: row = [4,0,3,1,2,5]
Output: 2
Explanation: The three couples form one cycle through the seat pairs, which takes two swaps to untangle.
Constraints
2n == row.length1 <= n <= 300 <= row[i] < 2nAll the elements of row are distinct
Hints for Couples Holding Hands
Hint 1
Look at seat pairs
(0,1),(2,3), …. Fixing a pair never needs to touch a pair that is already correct.Hint 2
Greedy: walk the pairs left to right; if the person in seat
2iis not next to their partner, swap the partner into seat2i + 1.Hint 3
Why is that optimal? Draw couples as nodes and each seat pair as an edge between the two couples sitting there. Each cycle of
ccouples needs exactlyc - 1swaps.
How to solve Couples Holding Hands
Treat each couple as a node and each seat pair as an edge joining the couples of its two occupants. Every node has degree 2, so the graph is a set of cycles, and a cycle of c couples needs exactly c - 1 swaps — which the left-to-right greedy achieves.
Approach
- Record the seat of every person in
pos. - For each pair of seats
(2i, 2i + 1): letpartner = row[2i] ^ 1. Ifrow[2i + 1]is already the partner, continue. - Otherwise swap the partner (at
pos[partner]) with the person in seat2i + 1, update both positions, and count one swap. - Return the count.
Why it works
Each greedy swap seats one couple correctly and shortens its cycle by one couple, so a cycle of length c takes c - 1 swaps, for a total of n - (number of cycles). No method can do better: a single swap changes two seat pairs and can raise the number of cycles by at most one, and the goal state has n cycles.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The partner of
xisx ^ 1(0↔1, 2↔3, …), notx + 1. - Keep the position array in sync after each swap, for both people moved.
- Seat pairs are fixed at even offsets — couples in seats 1 and 2 do not count as sitting together.
Reference solution
Python
from typing import List
def minSwapsCouples(row: List[int]) -> int:
r = list(row)
pos = [0] * len(r)
for i, p in enumerate(r):
pos[p] = i
swaps = 0
for i in range(0, len(r), 2):
partner = r[i] ^ 1
if r[i + 1] != partner:
j = pos[partner]
other = r[i + 1]
r[j], pos[other] = other, j
r[i + 1], pos[partner] = partner, i + 1
swaps += 1
return swapsJava
public static int minSwapsCouples(int[] row) {
int[] r = row.clone();
int[] pos = new int[r.length];
for (int i = 0; i < r.length; i++) pos[r[i]] = i;
int swaps = 0;
for (int s = 0; s < r.length; s += 2) {
int partner = r[s] ^ 1;
if (r[s + 1] != partner) {
int j = pos[partner], other = r[s + 1];
r[j] = other; pos[other] = j;
r[s + 1] = partner; pos[partner] = s + 1;
swaps++;
}
}
return swaps;
}C++
int minSwapsCouples(vector<int>& row) {
vector<int> r(row);
vector<int> pos(r.size());
for (int i = 0; i < (int)r.size(); i++) pos[r[i]] = i;
int swaps = 0;
for (int s = 0; s < (int)r.size(); s += 2) {
int partner = r[s] ^ 1;
if (r[s + 1] != partner) {
int j = pos[partner], other = r[s + 1];
r[j] = other; pos[other] = j;
r[s + 1] = partner; pos[partner] = s + 1;
swaps++;
}
}
return swaps;
}JavaScript
var minSwapsCouples = function(row) {
var r = row.slice();
var pos = new Array(r.length);
for (var i = 0; i < r.length; i++) pos[r[i]] = i;
var swaps = 0;
for (var s = 0; s < r.length; s += 2) {
var partner = r[s] ^ 1;
if (r[s + 1] !== partner) {
var j = pos[partner], other = r[s + 1];
r[j] = other; pos[other] = j;
r[s + 1] = partner; pos[partner] = s + 1;
swaps++;
}
}
return swaps;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 264 greedy problems · the whole catalogue
Learn the technique: Greedy Algorithms · Graph Data Structure