0630HardGreedyDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Relay Duos On One Bench

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_swaps_couples(seats: list[int]) -> int:

Java

public int minSwapsCouples(int[] seats)

The intended approach

Time O(n) — building the index and settling each bench are both linear in the number of seats.Space O(n) for the bib-to-seat index.

Record which seat holds each bib, then settle the benches from left to right. Look at the athlete in the even seat of the current bench: the bib of the partner differs from it only in the lowest bit. If the partner is not already in the odd seat, move the partner into that odd seat and send its former neighbour to the seat the partner vacated, counting one move and updating both index entries. A bench once settled is never touched again, so every later move only involves seats further right, and the count is the total returned.

Pythonentry point: min_swaps_couples

def min_swaps_couples(seats):
    # O(n) time, O(n) space: hold an index saying which seat each bib occupies.
    # Sweep the benches left to right. For the person in the even seat, look up
    # where the partner bib sits; if it is not the odd seat of this bench, trade
    # that person with whoever is in the odd seat and repair both index entries.
    where = [0] * len(seats)
    for i, bib in enumerate(seats):
        where[bib] = i
    moves = 0
    for i in range(0, len(seats), 2):
        partner = seats[i] ^ 1
        j = i + 1
        p = where[partner]
        if p != j:
            other = seats[j]
            seats[j] = partner
            seats[p] = other
            where[partner] = j
            where[other] = p
            moves += 1
    return moves

The obvious version

Treat every bench as a link between the two duos whose bibs share it and merge those duos with a disjoint-set structure. Count how many merged groups remain and subtract that from the number of duos.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_swaps_couples(seats):
    n = len(seats) // 2
    par = list(range(n))

    def find(x):
        while par[x] != x:
            par[x] = par[par[x]]
            x = par[x]
        return x

    groups = n
    for i in range(n):
        a = find(seats[2 * i] // 2)
        b = find(seats[2 * i + 1] // 2)
        if a != b:
            par[a] = b
            groups -= 1
    return n - groups

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in