Seat Every Pair Together

HardArrays & Hashing

Problem

A theatre row has 2m seats, grouped into m benches: seats 0 and 1 form bench 0, seats 2 and 3 form bench 1, and so on. row[s] is the id of the guest in seat s; ids are 0..2m-1, and guests 2k and 2k + 1 came together as a pair.

In one move, any two guests may swap seats. Return the minimum number of moves so that every pair shares a bench (in either order).

Example 1

Input:
row = [0, 2, 1, 3]
Output:
1

Swap guests 2 and 1: [0, 1, 2, 3].

Example 2

Input:
row = [3, 2, 0, 1]
Output:
0

Both pairs already share a bench.

Example 3

Input:
row = [0, 3, 2, 1]
Output:
1

Constraints

  • 2 ≤ row.length = 2m ≤ 10^4
  • row is a permutation of 0..2m-1.

Hint

Show the first hint

A guest's partner is id XOR 1. Look at the benches left to right: what must happen at a bench whose two guests are not a pair?

Walkthrough

How to approach it

01Clarify before coding

  • Who is whose partner? Guests 2k and 2k + 1, i.e. partner(x) = x XOR 1.
  • Can any two guests swap, not only neighbours? Yes.
  • Does order on a bench matter? No.

02Brute force

Search over seatings (BFS where each move is a swap) until all pairs are seated together.

Cost: Exponential: (2m)! seatings.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.