Min Cost to Connect All Points
You're given an array points where points[i] = [x, y] is a point on a 2-D plane. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|. Return the minimum total cost to connect all the points, so that there is exactly one path of connections between any two of them. All points are distinct.
Examples
points = [[0,0],[1,3],[4,0]] returns 8
Connecting (0,0) to each of the others costs 4 apiece, for a total of 8. Joining (1,3) and (4,0) directly would cost 6, so it isn't used.
points = [[-2,1],[0,0],[3,1],[1,-4]] returns 12
The cheapest connections are (-2,1) to (0,0) for 3, (0,0) to (3,1) for 4, and (0,0) to (1,-4) for 5.
points = [[5,5]] returns 0
A single point is already connected.
Constraints
- 1 <= points.length <= 1000
- -10^6 <= x, y <= 10^6
- All points are distinct.
Hints
Picture every pair of points joined by an edge weighted by their distance. What structure connects every node at the lowest total weight?
Build a minimum spanning tree. Kruskal's algorithm with union-find takes the cheapest edges first and skips any that would close a cycle.
Generate all pairs with their costs, sort by cost, and for each pair call union(i, j). When the union merges two sets, add the cost; stop after n - 1 merges.
Drill This: Your Approach First
Approach
This asks for a minimum spanning tree of the complete graph on the points. Kruskal's algorithm builds one: list all n(n - 1) / 2 edges with their Manhattan costs, sort them by cost, and add each edge whose endpoints are in different union-find sets, merging the sets as you go. Stop after n - 1 edges. Sorting dominates at O(n^2 log n) time with O(n^2) space for the edge list. Prim's algorithm with a plain distance array does the same job in O(n^2) time and O(n) space, which suits a dense graph like this one.
Time
O(n^2 log n)
Space
O(n^2)
Pitfall
Solutions
class Solution {
private int[] parent;
public int minCostConnectPoints(int[][] points) {
int n = points.length;
int[][] edges = new int[n * (n - 1) / 2][];
int e = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
edges[e++] = new int[] {cost, i, j};
}
}
Arrays.sort(edges, (a, b) -> Integer.compare(a[0], b[0]));
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int total = 0, used = 0;
for (int[] edge : edges) {
if (used == n - 1) break;
int a = find(edge[1]), b = find(edge[2]);
if (a == b) continue;
parent[a] = b;
total += edge[0];
used++;
}
return total;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}class Solution:
def minCostConnectPoints(self, points) -> int:
n = len(points)
edges = []
for i in range(n):
xi, yi = points[i]
for j in range(i + 1, n):
xj, yj = points[j]
edges.append((abs(xi - xj) + abs(yi - yj), i, j))
edges.sort()
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = used = 0
for cost, i, j in edges:
if used == n - 1:
break
a, b = find(i), find(j)
if a != b:
parent[a] = b
total += cost
used += 1
return total