Min Cost to Connect All Points
Min Cost to Connect All Points: connect every point with minimum total Manhattan edge cost.
- 1 <= points.length <= 1000
- -10⁶ <= xi, yi <= 10⁶
- All pairs (xi, yi) are distinct.
Intuition
Min cost to connect all points joins every point on a plane at minimum total cost, where connecting two points costs their Manhattan distance. The greedy instinct — link each point to its nearest neighbour — fails, producing disconnected clusters or redundant cycles rather than one connected structure.
The reframing is to see the geometry as a graph. Treat every point as a vertex and every pair as an edge weighted by Manhattan distance, giving a complete graph. Connecting all vertices for minimum total weight, with no redundant edges, is by definition a minimum spanning tree.
Once named, the algorithm is standard. Prim's suits this case particularly well:
- The graph is complete, so edges vastly outnumber vertices, and Prim's cost depends on vertices rather than on materialising all n² edges.
That matters practically. Kruskal's would require sorting every one of the n(n−1)/2 edges, which is wasteful when most will never be considered. Prim's grows one tree, computing distances from each newly absorbed point only as needed.
The correctness rests on the cut property: for any partition of the vertices, the lightest edge crossing it belongs to some minimum spanning tree. The tree-versus-rest split is exactly such a partition, so the cheapest edge leaving the tree is always safe to take.
Stop once n vertices have joined. Stale heap entries pointing at already-visited points are skipped rather than removed.
Whenever all locations must be connected and edge costs are additive, consider a minimum spanning tree. A dense implicit graph often favors Prim's algorithm because edges can be generated as vertices enter the tree.
Approach
Before reading on: price up what the direct approach costs here, then ask which edge is always safe to take across a cut. Aim for O(n^2 log n) time and O(n^2) space.
See why nearest-neighbour fails
Linking each point to its closest neighbour creates disconnected clusters and cycles rather than one spanning structure. Recognising that pushes you toward a real MST algorithm instead of a local rule.
Model the points as a complete graph
Every pair of points is an edge weighted by Manhattan distance |x1-x2| + |y1-y2|. Connecting all vertices at minimum total weight is the definition of a minimum spanning tree — naming it settles the algorithm.
Prefer Prim's for a dense graph
With n(n−1)/2 edges, Kruskal's would sort them all. Prim's cost scales with vertices and computes distances on demand from each absorbed point, which is far better suited to a complete graph.
Seed the heap at any point
Push (0, 0) — point zero joins at no cost. The starting choice is arbitrary, since a minimum spanning tree spans every vertex regardless of where the growth begins.
Take the cheapest crossing edge
Pop the minimum, skip it if the endpoint is already visited, otherwise add its cost and mark the point. The cut property guarantees the cheapest edge leaving the tree belongs to some MST, so no accepted edge is ever wrong.
Push distances from each newly added point
After absorbing a point, compute its Manhattan distance to every unvisited point and push those into the heap. Stale entries for points absorbed in the meantime are discarded when popped.
Cost of the approach
Each of the n absorptions pushes up to n edges, giving O(n² log n) time with a heap and O(n²) space. The O(n²) array-based Prim's without a heap is actually faster here — worth mentioning for a genuinely complete graph.
Solution & live demo
Common pitfalls
Adding costs for stale heap entries
cost, point = heappop(heap) total += cost
cost, point = heappop(heap)
if point in visited:
continue
total += costMultiple candidate edges can lead to the same vertex, but an MST accepts it only once.
Using Euclidean distance
distance = sqrt(dx * dx + dy * dy)
distance = abs(dx) + abs(dy)
The problem explicitly assigns Manhattan edge costs.
Stopping when the heap first empties incorrectly
while heap and len(visited) < n - 1:
while heap and len(visited) < n:
All n vertices, including the starting point, must be accepted.
Edge cases
The initial zero-cost entry visits it and the result remains zero.
The visited check accepts only the cheapest first entry and discards stale ones.
Absolute coordinate differences compute Manhattan distance without special handling.