LeetCode 1584: Min Cost to Connect All Points
LeetCode 1584 Solution Explanation
Explanation:
To solve this problem, we can use Kruskal's algorithm to find the minimum spanning tree (MST) of the given graph where each point is a vertex and the cost between two points is an edge. We will use the Manhattan distance as the weight of the edges. The total cost of connecting all points will be the sum of the weights of the edges in the MST.
Steps:
- Calculate the Manhattan distance between all pairs of points and store the distances along with their corresponding points' indices.
- Sort the distances in ascending order.
- Iterate through the sorted distances and add the edge to the MST if it does not create a cycle using Union-Find (Disjoint Set Union) data structure.
Time Complexity: O(n^2 log n) where n is the number of points. Space Complexity: O(n^2) for storing distances and O(n) for Union-Find.
:
LeetCode 1584 Solutions in Java, C++, Python
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
List<int[]> distances = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
distances.add(new int[]{i, j, dist});
}
}
Collections.sort(distances, (a, b) -> Integer.compare(a[2], b[2]));
int minCost = 0;
UnionFind uf = new UnionFind(n);
for (int[] dist : distances) {
if (uf.union(dist[0], dist[1])) {
minCost += dist[2];
}
}
return minCost;
}
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return false;
}
parent[rootX] = rootY;
return true;
}
}
}Interactive Code Editor for LeetCode 1584
Improve Your LeetCode 1584 Solution
Use the editor below to refine the provided solution for LeetCode 1584. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...