Partners Side by Side

Hard

At a banquet the guests sit in a single row, and the chairs are grouped into neighbouring pairs: chairs 0 and 1, chairs 2 and 3, and so on. Every guest came with a partner: guests 0 and 1 are a couple, 2 and 3 are a couple, and so on up to the last two numbers. The array seats describes the seating: seats[i] is the guest sitting in chair i. In one swap, any two guests trade chairs. Return the minimum number of swaps after which every couple occupies one pair of neighbouring chairs (2j and 2j + 1).

Example 1

seats=[1, 3, 0, 2] → 1

The table pairs are (1, 3) and (0, 2). Swapping guests 3 and 0 gives (1, 0) and (3, 2), so both couples sit together after one swap.

Example 2

seats=[5, 4, 2, 3, 1, 0] → 0

Every couple is already side by side, so no swaps are needed.

Example 3

seats=[0, 2, 4, 1, 3, 5] → 2

The pairs (0, 2), (4, 1) and (3, 5) are mixed up in a cycle: one swap is not enough, it takes two.

Constraints

2 ≤ len(seats) ≤ 10⁵, and the length is even
seats is a permutation of the numbers 0 to len(seats) − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Depth-First Search Breadth-First Search Union Find Graph

Similar problems

The Extra Link in a Rooted Tree Hard Which Machine to Cure Hard Which Machine to Unplug Hard News Through a Chain of Calls Hard Distances to the Ring Road Hard

Input

seats=[1, 3, 0, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.