hardGraphsPure DSA~30 min
Minimum Swaps to Seat Every Pair Together
Replicas are deployed in a row of slots, two per logical pair (ids 2x and 2x+1). You want each pair to occupy adjacent slots. Each swap exchanges any two slots; find the fewest swaps.
Problem
Given an array row of length 2N that is a permutation of 0..2N-1, where the pair for value v is v XOR 1, partners sit at indices (0,1), (2,3), ... Return the minimum number of swaps so that every pair occupies adjacent positions.
Input
An array row of length 2N, a permutation of integers 0..2N-1.
Output
An integer: the minimum number of swaps.
Constraints
- 2 <= row.length <= 60
- row.length is even
- row is a permutation of 0..row.length-1.
Examples
Example 1
Input
row = [0,2,1,3]
Output
1
Swap indices 1 and 2 to get [0,1,2,3]; both pairs are adjacent.
Example 2
Input
row = [3,2,0,1]
Output
0
Pairs (3,2) and (0,1) are already adjacent.