Show problems as
Classic problem #765HardGreedyDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Couples Holding Hands

Real-world version: Relay Duos On One Bench
Tracked in this browser only
Read Couples Holding Hands on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A relay squad of n duos boards a shuttle with 2n seats in one straight row, numbered 0 to 2n - 1. The two athletes of duo k wear the bibs 2k and 2k + 1. The list seats records the boarding order: seats[i] is the bib of the athlete now sitting in seat i, and every bib appears exactly once.

Seats 2i and 2i + 1 form bench i. One move picks any two seats; the two athletes in them stand up and take each other's place. Return the smallest number of moves that leaves both athletes of every duo on the same bench.

Examples

Example 1

Input
seats = [1, 4, 0, 5, 2, 3]
Output
1

Bench 0 holds bibs 1 and 4, bench 1 holds 0 and 5, bench 2 holds 2 and 3. Swapping the athletes in seats 1 and 2 gives [1, 0, 4, 5, 2, 3], where bench 0 holds duo 0, bench 1 holds duo 2 and bench 2 holds duo 1, so one move is enough.

Example 2

Input
seats = [5, 4, 1, 0, 3, 2]
Output
0

Bench 0 already holds bibs 5 and 4, which are duo 2; bench 1 holds 1 and 0, duo 0; bench 2 holds 3 and 2, duo 1. Every duo is together, so no move is needed.

Example 3

Input
seats = [0, 2, 4, 1, 3, 5]
Output
2

Swapping seats 1 and 3 gives [0, 1, 4, 2, 3, 5], then swapping seats 3 and 5 gives [0, 1, 4, 5, 3, 2]. Bench 0 holds duo 0, bench 1 holds duo 2 and bench 2 holds duo 1, so two moves suffice.

Constraints

  • 2n == seats.length
  • 2 <= n <= 30
  • 0 <= seats[i] < 2n
  • All the values in seats are different.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_swaps_couples(seats: list[int]) -> int:
Java
public int minSwapsCouples(int[] seats)

More on the same topics