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
0here), 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;
}
}