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:
![](https://spcdn.pages.dev/leetcode/problems/1584.Min%20Cost%20to%20Connect%20All%20Points/images/d.png)
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#
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#
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
}
|