LeetCode 1584: Min Cost to Connect All Points Solution
Master LeetCode problem 1584 (Min Cost to Connect All Points), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1584. Min Cost to Connect All Points
Problem 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.
:
Solution Code
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;
}
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1584 (Min Cost to Connect All Points)?
This page provides optimized solutions for LeetCode problem 1584 (Min Cost to Connect All Points) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1584 (Min Cost to Connect All Points)?
The time complexity for LeetCode 1584 (Min Cost to Connect All Points) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1584 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1584 in Java, C++, or Python.