Greedy
Depth-First Search
Breadth-First Search
Union Find
Graph
Description
There are n
couples sitting in 2n
seats arranged in a row and want to hold hands.
The people and seats are represented by an integer array row
where row[i]
is the ID of the person sitting in the ith
seat. 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)
.
Return 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.
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.
Constraints:
2n == row.length
2 <= n <= 30
n
is even.
0 <= row[i] < 2n
All the elements of row
are unique .
Solutions
Solution 1
Python3 Java C++ Go TypeScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def minSwapsCouples ( self , row : List [ int ]) -> int :
def find ( x : int ) -> int :
if p [ x ] != x :
p [ x ] = find ( p [ x ])
return p [ x ]
n = len ( row ) >> 1
p = list ( range ( n ))
for i in range ( 0 , len ( row ), 2 ):
a , b = row [ i ] >> 1 , row [ i + 1 ] >> 1
p [ find ( a )] = find ( b )
return n - sum ( i == find ( i ) for i in range ( n ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class Solution {
private int [] p ;
public int minSwapsCouples ( int [] row ) {
int n = row . length >> 1 ;
p = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
p [ i ] = i ;
}
for ( int i = 0 ; i < n << 1 ; i += 2 ) {
int a = row [ i ] >> 1 , b = row [ i + 1 ] >> 1 ;
p [ find ( a ) ] = find ( b );
}
int ans = n ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( i == find ( i )) {
-- ans ;
}
}
return ans ;
}
private int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ] );
}
return p [ x ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
int minSwapsCouples ( vector < int >& row ) {
int n = row . size () / 2 ;
int p [ n ];
iota ( p , p + n , 0 );
function < int ( int ) > find = [ & ]( int x ) -> int {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
};
for ( int i = 0 ; i < n << 1 ; i += 2 ) {
int a = row [ i ] >> 1 , b = row [ i + 1 ] >> 1 ;
p [ find ( a )] = find ( b );
}
int ans = n ;
for ( int i = 0 ; i < n ; ++ i ) {
ans -= i == find ( i );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 func minSwapsCouples ( row [] int ) int {
n := len ( row ) >> 1
p := make ([] int , n )
for i := range p {
p [ i ] = i
}
var find func ( int ) int
find = func ( x int ) int {
if p [ x ] != x {
p [ x ] = find ( p [ x ])
}
return p [ x ]
}
for i := 0 ; i < n << 1 ; i += 2 {
a , b := row [ i ] >> 1 , row [ i + 1 ] >> 1
p [ find ( a )] = find ( b )
}
ans := n
for i := range p {
if find ( i ) == i {
ans --
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 function minSwapsCouples ( row : number []) : number {
const n = row . length >> 1 ;
const p : number [] = Array ( n )
. fill ( 0 )
. map (( _ , i ) => i );
const find = ( x : number ) : number => {
if ( p [ x ] !== x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
};
for ( let i = 0 ; i < n << 1 ; i += 2 ) {
const a = row [ i ] >> 1 ;
const b = row [ i + 1 ] >> 1 ;
p [ find ( a )] = find ( b );
}
let ans = n ;
for ( let i = 0 ; i < n ; ++ i ) {
if ( i === find ( i )) {
-- ans ;
}
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 public class Solution {
private int [] p ;
public int MinSwapsCouples ( int [] row ) {
int n = row . Length >> 1 ;
p = new int [ n ];
for ( int i = 0 ; i < n ; ++ i ) {
p [ i ] = i ;
}
for ( int i = 0 ; i < n << 1 ; i += 2 ) {
int a = row [ i ] >> 1 ;
int b = row [ i + 1 ] >> 1 ;
p [ find ( a )] = find ( b );
}
int ans = n ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( p [ i ] == i ) {
-- ans ;
}
}
return ans ;
}
private int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
}
}
GitHub