Given the coordinates of several points on a 2D plane, connect all of them so every point is reachable from every other, at minimum total cost — where the cost to connect two points is their Manhattan distance.
Example
Input points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output 20
Key Pointers
"Connect all points at minimum cost, no cycles needed" is a minimum spanning tree (MST) problem.
Prim's algorithm grows the tree one cheapest edge at a time using a min-heap — a natural fit here since edges aren't given explicitly, they're implied between every pair of points.
Manhattan distance is just |x1-x2| + |y1-y2| — no square roots involved.
Step-by-Step Analysis
Start from point 0 and push (0, 0) — meaning cost 0 to reach point index 0 — onto a min-heap.
While fewer than n points are visited, pop the cheapest (cost, point) pair from the heap.
If that point is already visited, skip it (a stale heap entry); otherwise mark it visited and add its cost to the running total.
Push the Manhattan distance from the newly visited point to every still-unvisited point, and repeat until all n points are visited.
Complexity
Time: O(n² log n) — Space: O(n²)
Code
import heapq
def minCostConnectPoints(points: list[list[int]]) -> int:
n = len(points)
visited = set()
min_heap = [(0, 0)]
total_cost = 0
while len(visited) < n:
cost, i = heapq.heappop(min_heap)
if i in visited:
continue
visited.add(i)
total_cost += cost
for j in range(n):
if j not in visited:
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
heapq.heappush(min_heap, (dist, j))
return total_cost
Code Explanation
How the solution above works, piece by piece.
This is a minimum spanning tree problem where every pair of points is an edge weighted by Manhattan distance. The code uses Prim's algorithm.
The heap holds (cost, point) candidates for joining the tree; start with point 0 at cost 0.
Pop the cheapest candidate. If the point is already in the tree, skip it (a cheaper edge got there first).
Otherwise add it, pay its cost, and push edges from it to every point still outside the tree.
Stop once all n points are in. With a heap this is O(n² log n); every pair is considered because the graph is complete.
Visual Walkthrough
Running it on points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]:
Prim's algorithm grows one connected tree from point 0. At each step it adds the cheapest edge (Manhattan distance) from the tree to a point not yet in it. Four edges connect all five points for a total of 20.