765. Couples Holding Hands #

Problem #

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0...len(row)-1.

Problem Summary #

N couples sit in 2N consecutively arranged seats and want to hold each other’s hands. Calculate the minimum number of seat swaps needed so that every couple can sit side by side. One swap consists of choosing any two people and having them stand up and exchange seats. People and seats are represented by integers from 0 to 2N-1. The couples are numbered in order: the first couple is (0, 1), the second couple is (2, 3), and so on, with the last couple being (2N-2, 2N-1). The initial seating of these couples, row[i], is determined by the person initially sitting in the i-th seat.

Notes:

len(row) is even and its value is in the range [4, 60].
It is guaranteed that row is a permutation of the sequence 0…len(row)-1.

Solution Ideas #

Given an array, every two adjacent elements in the array represent a couple. Couple numbering starts from 0: 0 and 1 are a couple, 2 and 3 are a couple… These couples sit in a row, but they are not necessarily sitting together in pairs. The question asks how to swap seats the minimum number of times so that couples can sit together pairwise.
The breakthrough for this problem is how to find the minimum number of swaps. At first glance, there may be no clear idea. Intuition tells us that for this kind of difficult problem, the final conclusion or formula is very likely to be a very simple expression. (This problem is indeed such a case.) For now, ignore the minimum number of swaps and handle this problem in a normal way. Take an example: [3 1 4 0 2 5], scan from index 0 of the array.
```
  Initial state
    
  Set 0: 0, 1
  Set 1: 2, 3
  Set 2: 4, 5
```
3 and 1 are not a couple, so union() the sets where 3 and 1 are located. The set containing 3 is 1, and the set containing 1 is 0, so union() sets 0 and 1. Because couple 0 and couple 1 are in set 0, couple 2 and couple 3 are in set 1, and so on.
```
  Sets 0 and 1: 0, 1, 2, 3
  Set 2: 4, 5
```
Continue scanning backward. 4 and 0 are not in the same set. 4 is in set 3, and 0 is in set 0, so union() them.
```
  Sets 0, 1, and 2: 0, 1, 2, 3, 4, 5
```
In the above set-merging process, 2 merges were performed. This means the minimum number of swaps needed is 2. It can also be calculated by len(row)/2 - uf.count. len(row)/2 is the initial total number of sets, and uf.count is the number of sets remaining at the end. The difference between the two is the number of swaps in between.
The final implementation code is very simple. First, use union-find to union() every two adjacent elements together. Then scan the original array; each time, scan two adjacent elements, and perform union() according to the sets where the values of these two elements are located. After the scan is complete, the final answer can be obtained.
Looking back at this problem, why is it that adjusting each couple one by one from the beginning of the array to the end yields the minimum number of swaps? In fact, the idea behind this method is a greedy approach. Adjusting pairs one by one from the beginning to the end can ultimately achieve the minimum number of swaps. (The author does not know the specific proof.) After all swaps are done, the last couple must be correct and does not need to be swapped. (Because every previous pair has been adjusted, the last pair must be correct.)

Code #


package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

func minSwapsCouples(row []int) int {
	if len(row)&1 == 1 {
		return 0
	}
	uf := template.UnionFind{}
	uf.Init(len(row))
	for i := 0; i < len(row)-1; i = i + 2 {
		uf.Union(i, i+1)
	}
	for i := 0; i < len(row)-1; i = i + 2 {
		if uf.Find(row[i]) != uf.Find(row[i+1]) {
			uf.Union(row[i], row[i+1])
		}
	}
	return len(row)/2 - uf.TotalCount()
}