Description
There are n couples sitting in 2n seats arranged in a row. Return the minimum number of swaps so that every couple is sitting side by side.
Examples
Input:
row = [0,2,1,3]Output:
1Explanation:
Swap row[1] and row[2].
Input:
row = [3,2,0,1]Output:
0Explanation:
Edge case returning zero.
Input:
row = [5,4,3,2,1,0]Output:
3Explanation:
Three couples: (0,1), (2,3), (4,5). Currently arranged as [5,4,3,2,1,0]. Swapping positions 0 and 5 gives [0,4,3,2,1,5], then positions 1 and 4 gives [0,1,3,2,4,5], then positions 2 and 3 gives [0,1,2,3,4,5]. Three swaps are needed.
Constraints
- •
2n == row.length - •
2 ≤ n ≤ 30 - •
0 ≤ row[i] < 2n