Formatted question description: https://leetcode.ca/all/1584.html
1584. Min Cost to Connect All Points (Medium)
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
Example 3:
Input: points = [[0,0],[1,1],[1,0],[-1,1]] Output: 4
Example 4:
Input: points = [[-1000000,-1000000],[1000000,1000000]] Output: 4000000
Example 5:
Input: points = [[0,0]] Output: 0
Constraints:
1 <= points.length <= 1000
-106 <= xi, yi <= 106
- All pairs
(xi, yi)
are distinct.
Related Topics:
Union Find
Solution 1. Kruskal
The run time is too restrict. If you sort the edges then use Kruskal you will get TLE. The time complexity is O(N^2 * log(N^2))
.
We have to use min heap instead so that the time complexity is O(K * log(N^2))
where K
is the number of edges we need to scan to complete the tree. It’s much smaller than N^2
on average.
// OJ: https://leetcode.com/problems/min-cost-to-connect-all-points/
// Time: O(K * log(N^2))
// Space: O(N^2)
// Ref: https://leetcode.com/problems/min-cost-to-connect-all-points/discuss/843940/C%2B%2B-Minimum-Spanning-Tree-(Kruskal)
class UnionFind {
vector<int> id;
int size;
public:
UnionFind(int N) : id(N), size(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
--size;
}
bool connected(int a, int b) {
return find(a) == find(b);
}
int getSize() { return size; }
};
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0;
vector<array<int, 3>> E;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) E.push_back({ abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1]), i, j });
}
make_heap(begin(E), end(E), greater<array<int, 3>>());
UnionFind uf(N);
while (uf.getSize() > 1) {
pop_heap(begin(E), end(E), greater<array<int, 3>>());
auto [w, u, v] = E.back();
E.pop_back();
if (uf.connected(u, v)) continue;
uf.connect(u, v);
ans += w;
}
return ans;
}
};
We can also directly use priority_queue
.
// OJ: https://leetcode.com/problems/min-cost-to-connect-all-points/
// Time: O(K * log(N^2))
// Space: O(N^2)
class UnionFind {
vector<int> id;
int size;
public:
UnionFind(int N) : id(N), size(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
--size;
}
bool connected(int a, int b) {
return find(a) == find(b);
}
int getSize() { return size; }
};
class Solution {
typedef array<int, 3> Edge;
public:
int minCostConnectPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0;
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) q.push({ abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1]), i, j });
}
UnionFind uf(N);
while (uf.getSize() > 1) {
auto [w, u, v] = q.top();
q.pop();
if (uf.connected(u, v)) continue;
uf.connect(u, v);
ans += w;
}
return ans;
}
};
Solution 2. Prim
- Start from a random node (we use
0
here), add it to the minimum spanning tree (MST). - From all the edges connecting nodes in the MST and those outside of the MST, find the edge with the mimimal cost, and add the corresponding node to the MST.
- Repeat Step 2 until all the nodes are added into the MST.
// OJ: https://leetcode.com/problems/min-cost-to-connect-all-points/
// Time: O(N^2)
// Space: O(N)
// Ref: https://leetcode.com/problems/min-cost-to-connect-all-points/discuss/843921/PythonGolang-Just-add-points-greedily
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0, cur = 0;
vector<int> dist(N, INT_MAX), seen(N);
for (int i = 0; i < N - 1; ++i) {
int x = A[cur][0], y = A[cur][1];
seen[cur] = 1;
for (int j = 0; j < N; ++j) {
if (seen[j]) continue;
dist[j] = min(dist[j], abs(A[j][0] - x) + abs(A[j][1] - y));
}
cur = min_element(begin(dist), end(dist)) - begin(dist);
ans += dist[cur];
dist[cur] = INT_MAX;
}
return ans;
}
};
Java
class Solution {
public int minCostConnectPoints(int[][] points) {
if (points == null || points.length <= 1)
return 0;
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] array1, int[] array2) {
return array1[2] - array2[2];
}
});
int length = points.length;
int[][] distances = new int[length][length];
for (int i = 0; i < length; i++) {
int[] point1 = points[i];
for (int j = i + 1; j < length; j++) {
int[] point2 = points[j];
int distance = manhattanDistance(point1, point2);
priorityQueue.offer(new int[]{i, j, distance});
distances[i][j] = distance;
distances[j][i] = distance;
}
}
int[] parents = new int[length];
for (int i = 0; i < length; i++)
parents[i] = i;
int minCost = 0;
int size = length;
while (size > 1) {
int[] array = priorityQueue.poll();
int index1 = array[0], index2 = array[1], distance = array[2];
if (find(parents, index1) != find(parents, index2)) {
union(parents, index1, index2);
minCost += distance;
size--;
}
}
return minCost;
}
public int manhattanDistance(int[] point1, int[] point2) {
return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
}
public void union(int[] parents, int index1, int index2) {
parents[find(parents, index1)] = find(parents, index2);
}
public int find(int[] parents, int index) {
while (parents[index] != index) {
parents[index] = parents[parents[index]];
index = parents[index];
}
return index;
}
}