Description
Connect all 2D integer points using edges costing their Manhattan distance, |x1 - x2| + |y1 - y2|. Return the smallest total cost that makes every point reachable.
Solution
def min_cost_connect_points(points):
n = len(points)
costs = [float("inf")] * n
used = [False] * n
costs[0] = 0
total = 0
for _ in range(n):
node = min((i for i in range(n) if not used[i]), key=lambda i: costs[i])
total += costs[node]
used[node] = True
x, y = points[node]
for i, (a, b) in enumerate(points):
if not used[i]:
costs[i] = min(costs[i], abs(x - a) + abs(y - b))
return totalExamples
Example 1
- Input
[[[0,0],[2,2],[3,10],[5,2],[7,0]]]- Output
20
A minimum spanning tree has cost 20.
Example 2
- Input
[[[0,0],[1,1]]]- Output
2
The only needed connection has Manhattan distance 2.
Example 3
- Input
[[[3,4]]]- Output
0
One point needs no edge.
Approach
Use Prim's algorithm without materializing all edges. Track each unconnected point's cheapest link to the current tree. Select the cheapest such point, add its cost, and update remaining distances.
Time & space
O(n^2) time and O(n) auxiliary space, where n is point count.