1584. Min Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

1
2
3
4
5
6
7
8
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.

ex1

ex2

1
2
3
4
Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

1
2
3
4
Example 3:

Input: points = [[0,0],[1,1],[1,0],[-1,1]]
Output: 4

1
2
3
4
Example 4:

Input: points = [[-1000000,-1000000],[1000000,1000000]]
Output: 4000000

1
2
3
4
Example 5:

Input: points = [[0,0]]
Output: 0

Constraints:

1 <= points.length <= 1000
-106 <= xi, yi <= 106
All pairs (xi, yi) are distinct.

Solution

 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    int[] a;
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = i;
        }
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j)  {
                    int[] a = points[i];
                    int[] b = points[j];
                    int w = Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
                    pq.add(new Edge(i, j, w));
                }
            }
        }
        
        int sum = 0;
        while (pq.size() > 0) {
            Edge e = pq.poll();
            if (!same(e.a, e.b)) {
                union(e.a, e.b);
                sum += e.w;
            }
        }        
        return sum;
    }
    
    boolean same(int p, int q) {
        return find(p) == find(q);
    }
    
    int find(int p) {
        while (a[p] != p) {
            p = a[p];
            a[p] = a[a[p]];
        }
        return p;
    }
    
    void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);
        
        a[qid] = pid;
    }
    
    class Edge implements Comparable<Edge> {
        int a;
        int b;
        int w;
        
        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
        
        public int compareTo(Edge other) {
            return Integer.compare(this.w, other.w);
        }
    }
}

Solution#

Solution