leetcode 765 - Couples Holding Hands | Mengwen's blog
We first assign groups to elements in the array.
For example, given array [2, 1, 5, 0, 3, 4]
, we assign groups as the following:
[0, 1]
: group 0
[2, 3]
: group 2
[4, 5]
: group 4
To get the group number for a given array element, we can use arr[i] & (~0x1)
.
As a result, if we represent [2, 1, 5, 0, 3, 4]
in group labels, we get [2, 0, 4, 0, 2, 4]
.
We visualize each group as a vertax of a undirected graph.
The initial connection of these vertaxes are determined by the pairs in the given array.
For example, if the array is [0, 0, 2, 2, 4, 4]
, we get the following graph:
graph 0
If the array is [2, 0, 4, 0, 2, 4]
, we get:
graph 1
Assume the size of the input array is N
, If all the couples are seat next to each other, we want the graph to have exactly N / 2
connected components as shown in the [0, 0, 2, 2, 4, 4]
graph.
After we convert the input array into an undirected graph, we convert the problem to:
Given this undirected graph with (N / 2) vertices, and at most two edges for a vertex, what is the minimum swaps needed to convert this graph to a graph that has exactly (N / 2) connected components?
We can observe that, for the given kind of graph, every swap is guaranteed to break one vertex free if it is in a connected component, and thus, increase the total number of connected component by 1
.
For example, for the array [2, 0, 4, 0, 2, 4]
, after we swap idx 0
with idx 3
, we get [0, 0, 4, 2, 2, 4]
. By doing this, we break vertex 0
free, and increase the connected component count from 1
to 2
.
As a result, we can conclude that (the # of components we increased) == (the # of swaps we have to do)
Our gaol is to increase the total number of components to N / 2
. Thus we have (origional # of components) + (# of components we have to increase) == N / 2
.
As a result, we have:
(# of swaps we have to do) == (# of components we have to increase) == N / 2 - (origional # of components)
So, the problem now is converted to find (origional # of connected components)
in this undirected graph.
In order to find the origional number of connected components, we can do the following:
If we start with N / 2
connected components, each time we find a new edge between two components, we have to reduce the number of our connected components by 1
.
For example, for array [0, 2, 2, 0, 4, 4]
, we should have 2
connected components: 0 - 2
and 4
. If we start our component count at 3
, when we see the first pair [0, 2]
, we know that component 0
and 2
are connected, so we reduce our component count to 2
. Then, we see pair [2, 0]
, but since we already handled [0, 2]
, we don't have to handle [2, 0]
again since the graph is undirected. So, in the end, we find out that we have 2
connected components in the graph generated by [0, 2, 2, 0, 4, 4]
.
To achieve this, we can use Union-Find method.
We inspect one pair every time. If the two elements are not already in one group, we know that a new edge is now being added, which means we have to decrease the count of our connected components by 1
. Then, we union these two groups.
Read full article from leetcode 765 - Couples Holding Hands | Mengwen's blog