Union Find
Graph
Array
Minimum Spanning Tree
Description
You are given an array points
representing integer coordinates of some points on a 2D-plane, where points[i] = [xi , yi ]
.
The cost of connecting two points [xi , yi ]
and [xj , yj ]
is the manhattan distance between them: |xi - xj | + |yi - yj |
, where |val|
denotes the absolute value of val
.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Example 1:
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:
We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.
Example 2:
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Constraints:
1 <= points.length <= 1000
-106 <= xi , yi <= 106
All pairs (xi , yi )
are distinct.
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution :
def minCostConnectPoints ( self , points : List [ List [ int ]]) -> int :
n = len ( points )
g = [[ 0 ] * n for _ in range ( n )]
dist = [ inf ] * n
vis = [ False ] * n
for i , ( x1 , y1 ) in enumerate ( points ):
for j in range ( i + 1 , n ):
x2 , y2 = points [ j ]
t = abs ( x1 - x2 ) + abs ( y1 - y2 )
g [ i ][ j ] = g [ j ][ i ] = t
dist [ 0 ] = 0
ans = 0
for _ in range ( n ):
i = - 1
for j in range ( n ):
if not vis [ j ] and ( i == - 1 or dist [ j ] < dist [ i ]):
i = j
vis [ i ] = True
ans += dist [ i ]
for j in range ( n ):
if not vis [ j ]:
dist [ j ] = min ( dist [ j ], g [ i ][ j ])
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
31
32
33
34
35
36
37 class Solution {
public int minCostConnectPoints ( int [][] points ) {
final int inf = 1 << 30 ;
int n = points . length ;
int [][] g = new int [ n ][ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
int x1 = points [ i ][ 0 ] , y1 = points [ i ][ 1 ] ;
for ( int j = i + 1 ; j < n ; ++ j ) {
int x2 = points [ j ][ 0 ] , y2 = points [ j ][ 1 ] ;
int t = Math . abs ( x1 - x2 ) + Math . abs ( y1 - y2 );
g [ i ][ j ] = t ;
g [ j ][ i ] = t ;
}
}
int [] dist = new int [ n ] ;
boolean [] vis = new boolean [ n ] ;
Arrays . fill ( dist , inf );
dist [ 0 ] = 0 ;
int ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
int j = - 1 ;
for ( int k = 0 ; k < n ; ++ k ) {
if ( ! vis [ k ] && ( j == - 1 || dist [ k ] < dist [ j ] )) {
j = k ;
}
}
vis [ j ] = true ;
ans += dist [ j ] ;
for ( int k = 0 ; k < n ; ++ k ) {
if ( ! vis [ k ] ) {
dist [ k ] = Math . min ( dist [ k ] , g [ j ][ k ] );
}
}
}
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
31
32
33
34
35
36
37
38 class Solution {
public :
int minCostConnectPoints ( vector < vector < int >>& points ) {
int n = points . size ();
int g [ n ][ n ];
for ( int i = 0 ; i < n ; ++ i ) {
int x1 = points [ i ][ 0 ], y1 = points [ i ][ 1 ];
for ( int j = i + 1 ; j < n ; ++ j ) {
int x2 = points [ j ][ 0 ], y2 = points [ j ][ 1 ];
int t = abs ( x1 - x2 ) + abs ( y1 - y2 );
g [ i ][ j ] = t ;
g [ j ][ i ] = t ;
}
}
int dist [ n ];
bool vis [ n ];
memset ( dist , 0x3f , sizeof ( dist ));
memset ( vis , false , sizeof ( vis ));
dist [ 0 ] = 0 ;
int ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
int j = -1 ;
for ( int k = 0 ; k < n ; ++ k ) {
if ( ! vis [ k ] && ( j == -1 || dist [ k ] < dist [ j ])) {
j = k ;
}
}
vis [ j ] = true ;
ans += dist [ j ];
for ( int k = 0 ; k < n ; ++ k ) {
if ( ! vis [ k ]) {
dist [ k ] = min ( dist [ k ], g [ j ][ k ]);
}
}
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43 func minCostConnectPoints ( points [][] int ) ( ans int ) {
n := len ( points )
g := make ([][] int , n )
vis := make ([] bool , n )
dist := make ([] int , n )
for i := range g {
g [ i ] = make ([] int , n )
dist [ i ] = 1 << 30
}
for i := range g {
x1 , y1 := points [ i ][ 0 ], points [ i ][ 1 ]
for j := i + 1 ; j < n ; j ++ {
x2 , y2 := points [ j ][ 0 ], points [ j ][ 1 ]
t := abs ( x1 - x2 ) + abs ( y1 - y2 )
g [ i ][ j ] = t
g [ j ][ i ] = t
}
}
dist [ 0 ] = 0
for i := 0 ; i < n ; i ++ {
j := - 1
for k := 0 ; k < n ; k ++ {
if ! vis [ k ] && ( j == - 1 || dist [ k ] < dist [ j ]) {
j = k
}
}
vis [ j ] = true
ans += dist [ j ]
for k := 0 ; k < n ; k ++ {
if ! vis [ k ] {
dist [ k ] = min ( dist [ k ], g [ j ][ k ])
}
}
}
return
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
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
31
32
33
34
35 function minCostConnectPoints ( points : number [][]) : number {
const n = points . length ;
const g : number [][] = Array ( n )
. fill ( 0 )
. map (() => Array ( n ). fill ( 0 ));
const dist : number [] = Array ( n ). fill ( 1 << 30 );
const vis : boolean [] = Array ( n ). fill ( false );
for ( let i = 0 ; i < n ; ++ i ) {
const [ x1 , y1 ] = points [ i ];
for ( let j = i + 1 ; j < n ; ++ j ) {
const [ x2 , y2 ] = points [ j ];
const t = Math . abs ( x1 - x2 ) + Math . abs ( y1 - y2 );
g [ i ][ j ] = t ;
g [ j ][ i ] = t ;
}
}
let ans = 0 ;
dist [ 0 ] = 0 ;
for ( let i = 0 ; i < n ; ++ i ) {
let j = - 1 ;
for ( let k = 0 ; k < n ; ++ k ) {
if ( ! vis [ k ] && ( j === - 1 || dist [ k ] < dist [ j ])) {
j = k ;
}
}
vis [ j ] = true ;
ans += dist [ j ];
for ( let k = 0 ; k < n ; ++ k ) {
if ( ! vis [ k ]) {
dist [ k ] = Math . min ( dist [ k ], g [ j ][ k ]);
}
}
}
return ans ;
}
Solution 2
Python3 Java C++ Go
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 class Solution :
def minCostConnectPoints ( self , points : List [ List [ int ]]) -> int :
def find ( x : int ) -> int :
if p [ x ] != x :
p [ x ] = find ( p [ x ])
return p [ x ]
n = len ( points )
g = []
for i , ( x1 , y1 ) in enumerate ( points ):
for j in range ( i + 1 , n ):
x2 , y2 = points [ j ]
t = abs ( x1 - x2 ) + abs ( y1 - y2 )
g . append (( t , i , j ))
p = list ( range ( n ))
ans = 0
for cost , i , j in sorted ( g ):
pa , pb = find ( i ), find ( j )
if pa == pb :
continue
p [ pa ] = pb
ans += cost
n -= 1
if n == 1 :
break
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
31
32
33
34
35
36
37
38
39
40 class Solution {
private int [] p ;
public int minCostConnectPoints ( int [][] points ) {
int n = points . length ;
List < int []> g = new ArrayList <> ();
for ( int i = 0 ; i < n ; ++ i ) {
int x1 = points [ i ][ 0 ] , y1 = points [ i ][ 1 ] ;
for ( int j = i + 1 ; j < n ; ++ j ) {
int x2 = points [ j ][ 0 ] , y2 = points [ j ][ 1 ] ;
g . add ( new int [] { Math . abs ( x1 - x2 ) + Math . abs ( y1 - y2 ), i , j });
}
}
g . sort ( Comparator . comparingInt ( a -> a [ 0 ] ));
p = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
p [ i ] = i ;
}
int ans = 0 ;
for ( int [] e : g ) {
int cost = e [ 0 ] , i = e [ 1 ] , j = e [ 2 ] ;
if ( find ( i ) == find ( j )) {
continue ;
}
p [ find ( i ) ] = find ( j );
ans += cost ;
if ( -- n == 1 ) {
return ans ;
}
}
return 0 ;
}
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
24
25
26
27
28
29
30
31
32
33 class Solution {
public :
vector < int > p ;
int minCostConnectPoints ( vector < vector < int >>& points ) {
int n = points . size ();
vector < vector < int >> g ;
for ( int i = 0 ; i < n ; ++ i ) {
int x1 = points [ i ][ 0 ], y1 = points [ i ][ 1 ];
for ( int j = i + 1 ; j < n ; ++ j ) {
int x2 = points [ j ][ 0 ], y2 = points [ j ][ 1 ];
g . push_back ({ abs ( x1 - x2 ) + abs ( y1 - y2 ), i , j });
}
}
sort ( g . begin (), g . end ());
p . resize ( n );
for ( int i = 0 ; i < n ; ++ i ) p [ i ] = i ;
int ans = 0 ;
for ( auto & e : g ) {
int cost = e [ 0 ], i = e [ 1 ], j = e [ 2 ];
if ( find ( i ) == find ( j )) continue ;
p [ find ( i )] = find ( j );
ans += cost ;
if ( -- n == 1 ) return ans ;
}
return 0 ;
}
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 func minCostConnectPoints ( points [][] int ) int {
n := len ( points )
var g [][] int
for i , p := range points {
x1 , y1 := p [ 0 ], p [ 1 ]
for j := i + 1 ; j < n ; j ++ {
x2 , y2 := points [ j ][ 0 ], points [ j ][ 1 ]
g = append ( g , [] int { abs ( x1 - x2 ) + abs ( y1 - y2 ), i , j })
}
}
sort . Slice ( g , func ( i , j int ) bool {
return g [ i ][ 0 ] < g [ j ][ 0 ]
})
ans := 0
p := make ([] int , n )
for i := range p {
p [ i ] = i
}
var find func ( x int ) int
find = func ( x int ) int {
if p [ x ] != x {
p [ x ] = find ( p [ x ])
}
return p [ x ]
}
for _ , e := range g {
cost , i , j := e [ 0 ], e [ 1 ], e [ 2 ]
if find ( i ) == find ( j ) {
continue
}
p [ find ( i )] = find ( j )
ans += cost
n --
if n == 1 {
return ans
}
}
return 0
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
GitHub