1584. Min Cost to Connect All Points

Posted on Edited on In

1584. Min Cost to Connect All Points

Description

Difficulty: Medium

Related Topics: Array, Union Find, Graph, Minimum Spanning Tree

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:

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

1
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.

Hints/Notes

  • 2023/09/03
  • Kruskal’s algorithm: sort the edges, and check if points of the edge with minimum cost has been connected
  • Prim’s algorithm: cut points, keep adding edges and find the edge with minimum cost
  • cpp sort performance is worse than priority queue
  • Use count(number of separate items) to return early
  • No solution from 0x3F

Solution

Language: C++

Kruskal’s algorithm

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
class Solution {
public:
    vector<int> parent;

    int minCostConnectPoints(vector<vector<int>>& points) {
        vector<vector<int>> edges;
        int count = points.size();
        for (int i = 0; i < points.size(); i++) {
            parent.push_back(i);
        }
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                int distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                edges.push_back({distance, i, j});
            }
        }

        priority_queue pq(edges.begin(), edges.end(), greater<vector<int>>());

        int sum = 0;

        while (!pq.empty() && count > 1) {
            auto edge = pq.top();
            pq.pop();
            int p = edge[1];
            int q = edge[2];
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                continue;
            } else {
                parent[rootP] = rootQ;
                sum += edge[0];
                count--;
            }
        }
        return sum;
    }

    int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }
};

Prim’s algorithm

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
class Solution {
public:
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    vector<vector<vector<int>>> edges;
    vector<bool> visited;

    int minCostConnectPoints(vector<vector<int>>& points) {
        int size = points.size();
        edges = vector<vector<vector<int>>>(size, vector<vector<int>>());
        visited = vector<bool>(size, false);
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                int distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                edges[i].push_back({distance, j});
                edges[j].push_back({distance, i});
            }
        }

        int sum = 0;
        int count = 1;
        cut(0);
        visited[0] = true;

        while (!pq.empty()) {
            auto edge = pq.top();
            pq.pop();
            int to = edge[1];
            if (visited[to]) {
                continue;
            }
            int w = edge[0];
            sum += w;
            count++;
            if (count == size) break;
            cut(to);
            visited[to] = true;
        }

        return sum;
    }

    void cut(int node) {
        for (auto edge : edges[node]) {
            int to = edge[1];
            if (!visited[to]) {
                int w = edge[0];
                pq.push({w, to});
            }
        }
    }
};