Couples Holding Hands

Hard
1458.

Couples Holding Hands

Couples Holding Hands is a hard coding problem on greedy, graph and union find, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 30
  • 0 <= row[i] < 2n
  • All the elements of row are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} row
 * @return {number}
 */
var minSwapsCouples = function(row) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 30
  • 0 <= row[i] < 2n
  • All the elements of row are distinct

Hints for Couples Holding Hands

  1. Hint 1

    Look at seat pairs (0,1), (2,3), …. Fixing a pair never needs to touch a pair that is already correct.

  2. Hint 2

    Greedy: walk the pairs left to right; if the person in seat 2i is not next to their partner, swap the partner into seat 2i + 1.

  3. 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 c couples needs exactly c - 1 swaps.

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

  1. Record the seat of every person in pos.
  2. For each pair of seats (2i, 2i + 1): let partner = row[2i] ^ 1. If row[2i + 1] is already the partner, continue.
  3. Otherwise swap the partner (at pos[partner]) with the person in seat 2i + 1, update both positions, and count one swap.
  4. 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 x is x ^ 1 (0↔1, 2↔3, …), not x + 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 swaps

Java

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